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.

  • $\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 Mar 10 '14 at 19:58
  • $\begingroup$ You should provide some background and explain why you are interested in this problem. $\endgroup$ – Kaveh Mar 10 '14 at 23:28

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.

  • $\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 Mar 9 '14 at 23:33
  • $\begingroup$ I see the modification now: $(x \vee y) \wedge (x \vee z) \wedge \neg x$. Thank you again. $\endgroup$ – mathemagic Mar 9 '14 at 23:55

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

  • $\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 Mar 10 '14 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 Mar 11 '14 at 17:31

Your Answer

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

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