Consider a naive MAX SAT approximation algorithm:
- pick a literal $l$ which appears in maximum number of clauses
- set the corresponding variable of $l$, such that all clauses containing $l$ are satisfied
- 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.