4
$\begingroup$

Consider a naive MAX SAT approximation algorithm:

  1. pick a literal $l$ which appears in maximum number of clauses
  2. set the corresponding variable of $l$, such that all clauses containing $l$ are satisfied
  3. repeat on the reduced formula until no variables remain

What is the approximation factor of the algorithm?

It's easy to show by induction, that at least half of all clauses will end up sattisfied. But I can't find a tight example with only 1/2 clauses sattisfied and all clauses satisfiable. I expect, that the approximation ratio is better than 1/2, but I can neither prove it nor disprove it.

Thank you very much.

Improve this question
$\endgroup$
2
  • $\begingroup$ It really is only a $\frac{1}{2}$-approximation. The tight example is $(x_1 \vee x_2) \wedge \neg x_1$ with $x_1 \leftarrow 1$. $\endgroup$
    – mathemagic
    Commented Mar 10, 2014 at 19:58
  • $\begingroup$ You should provide some background and explain why you are interested in this problem. $\endgroup$
    – Kaveh
    Commented Mar 10, 2014 at 23:28

2 Answers 2

Reset to default
8
$\begingroup$

To complement the other answer: Costello, Shapira and Tetali showed that the expected approximation ration achieved by Johnson's algorithm on a random permutation of the variables is strictly better than $\frac{2}{3}$. Poloczek and Schnitger showed that another randomized version of the algorithm has expected approximation ratio $\frac{3}{4}$, and that the random permutation version does worse than $\frac{3}{4}$.

By the way do not feel bad about getting stuck on this. Proving an approximation ratio better than $\frac{1}{2}$ for this algorithm was an open problem for a while.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you both. The Johnson's algorihm, as I find it, usually has the order of variables determined in advance. That leads to tight examples for 2/3 ratio such as $(x \vee \neg y) \wedge (\neg x \vee y) \wedge \neg y$ where we set $x=1, y=0$. However, such example doesn't work for the algorithm described. Do you by chance see, how to adapt it? $\endgroup$
    – mathemagic
    Commented Mar 9, 2014 at 23:33
  • $\begingroup$ I see the modification now: $(x \vee y) \wedge (x \vee z) \wedge \neg x$. Thank you again. $\endgroup$
    – mathemagic
    Commented Mar 9, 2014 at 23:55
5
$\begingroup$

The described algorithm is actually Johnson's algorithm (with order on the vertices) which is known to achieve$\frac{2}{3} ratio$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Johnson's algorithm is in fact better in some details, which make it a $\frac{2}{3}$-apx. The naive algorithm described is only a $\frac{1}{2}$-apx. Consider the following example: $(x_1 \vee x_2) \wedge \neg x_1$. $\endgroup$
    – mathemagic
    Commented Mar 10, 2014 at 19:56
  • $\begingroup$ That's a good pont: Johnson's algorithm goes over variables, and for each chooses the assignment that satisfies more new clauses. $\endgroup$
    – Sasho Nikolov
    Commented Mar 11, 2014 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.