MAXSAT approximation

Question

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.

• Yuval Filmus: Presumably later on you will be shown more sophisticated randomized approximation algorithms.

Answer 1

I won't speculate about your teacher's reasons for including the random assignment algorithm over yours. However, one advantage of random assignment is that, if every clause has at least $k$ literals, it's actually a $(1-2^{-k})$-approximation (Wikipedia cites this to Vazirani's book). Your suggestion is still only a $\tfrac12$-approximation in this case (consider a formula where half the variables appear only in clauses where every literal is positive and the rest appear only in clauses where every literal is negative, and half the clauses are all-positive, half all-negative).