<p>To complement the other answer: <a href="http://dl.acm.org/citation.cfm?id=2133036.2133086">Costello, Shapira and Tetali</a> 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}$. <a href="http://dl.acm.org/citation.cfm?id=2133087">Poloczek and Schnitger</a> 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}$. </p>

<p>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.</p>

CC BY-SA 3.0
2014-03-09T23:33:52.520Z
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
CC BY-SA 3.0
2014-03-09T23:55:17.223Z
I see the modification now: $(x \vee y) \wedge (x \vee z) \wedge \neg x$. Thank you again.
mathemagic
CC BY-SA 3.0
2014-03-09T23:27:12.627Z
2014-03-09T23:27:12.627Z
Sasho Nikolov
<p>The described algorithm is actually Johnson's algorithm (with order on the vertices) which is known to achieve<a href="http://www.researchgate.net/publication/222467398_Tight_Bound_on_Johnson%27s_Algorithm_for_Maximum_Satisfiability/file/5046351cbf32169123.pdf">$\frac{2}{3} ratio$</a>.</p>

CC BY-SA 3.0
2014-03-10T19:56:22.910Z
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
CC BY-SA 3.0
2014-03-11T17:31:20.523Z
That's a good pont: Johnson's algorithm goes over variables, and for each chooses the assignment that satisfies more new clauses.
Sasho Nikolov
CC BY-SA 3.0
2014-03-09T23:07:21.570Z
2014-03-09T23:07:21.570Z
R B
<p>Consider a naive MAX SAT approximation algorithm:</p>

<ol>
<li>pick a literal $l$ which appears in maximum number of clauses</li>
<li>set the corresponding variable of $l$, such that all clauses containing $l$ are satisfied</li>
<li>repeat on the reduced formula until no variables remain</li>
</ol>

<p>What is the approximation factor of the algorithm?</p>

<p>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.</p>

<p>Thank you very much.</p>

CC BY-SA 3.0
2014-03-10T19:58:19.580Z
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
CC BY-SA 3.0
2014-03-10T23:28:05.210Z
You should provide some background and explain why you are interested in this problem.
Kaveh
<approximation-algorithms><approximation><max2sat>
Greedy MAX SAT approximation ratio
mathemagic
# Greedy MAX SAT approximation ratio

(Asked by: username_0 on 2014-03-09)

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.

**Tags:** approximation-algorithms, approximation, max2sat
> **Comments:**
> **username_0**: 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$.  
> **username_1**: You should provide some background and explain why you are interested in this problem.  

---

## 2 answers

### Answer by username_2 on 2014-03-09. Score: 8

To complement the other answer: [Costello, Shapira and Tetali](http://dl.acm.org/citation.cfm?id=2133036.2133086) 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](http://dl.acm.org/citation.cfm?id=2133087) 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.

> **Comments:**
> **username_0**: 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?  
> **username_0**: I see the modification now: $(x \vee y) \wedge (x \vee z) \wedge \neg x$. Thank you again.  

---

### Answer by username_3 on 2014-03-09. Score: 5

The described algorithm is actually Johnson's algorithm (with order on the vertices) which is known to achieve[$\frac{2}{3} ratio$](http://www.researchgate.net/publication/222467398_Tight_Bound_on_Johnson%27s_Algorithm_for_Maximum_Satisfiability/file/5046351cbf32169123.pdf).

> **Comments:**
> **username_0**: 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$.  
> **username_2**: That's a good pont: Johnson's algorithm goes over variables, and for each chooses the assignment that satisfies more new clauses.  

---

