Greedy MAX SAT approximation ratio 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.
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.