We have been studying a 1/2-approximation for MAXSAT which runs in expected polynomial time, by randomly assigning True/False to each variable and repeating until we reach an assignment with at least half of clauses satisfied.
I don't understand why the algorithm needs to be so complicated. Why does the following not give a 1/2-approximation for MAXSAT in guaranteed linear time?
- Let $m$ be the number of clauses in the formula.
- Set all variables to true. Count the number of satisfied clauses. If it's at least $m/2$ then return this assignment.
- Set all variables to false. Return this assignment.
Every clause contains at least one literal which will be satisfied either by setting a variable to true or a variable to false. Thus the two assignments satisfy a total of at least $m$ clauses so at least one of them satisfies $\ge m/2$ clauses.