0
$\begingroup$

$MAX2SAT$ has a $0.9401$ to $0.9402$ approximation algorithm which is conjectured to be optimal by $UGC$ while there is a balanced $MAX2SAT$ bound of $0.943$ approximation which is conjectured to be optimal by $UGC$.

  1. For other values of $k$ do we know the optimal values conjectured by $UGC$ for both balanced and general situations and the status of algorithmically achievable results known?
  1. A sanity check for $MAXSAT$: For $MAXSAT$ it is $NP$-hard to beat $7/8$ approximation and we have an algorithm which achieves $7/8$ and do we know $UGC$ provides the same bound for both balanced and general situations (I am unable to locate what $UGC$ says about $MAXSAT$ and we know if $UGC$ says a strictly lower than $7/8$ bound then trivially $UGC$ is false and so this sanity check)?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.