4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Presumably later on you will be shown more sophisticated randomized approximation algorithms. $\endgroup$ – Yuval Filmus Apr 30 at 16:21
6
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.