Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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$. –  mathemagic Mar 10 at 19:58
    
You should provide some background and explain why you are interested in this problem. –  Kaveh Mar 10 at 23:28
add comment

2 Answers 2

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.

share|improve this answer
    
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? –  mathemagic Mar 9 at 23:33
    
I see the modification now: $(x \vee y) \wedge (x \vee z) \wedge \neg x$. Thank you again. –  mathemagic Mar 9 at 23:55
add comment

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

share|improve this answer
    
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$. –  mathemagic Mar 10 at 19:56
    
That's a good pont: Johnson's algorithm goes over variables, and for each chooses the assignment that satisfies more new clauses. –  Sasho Nikolov Mar 11 at 17:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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