6
$\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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Presumably later on you will be shown more sophisticated randomized approximation algorithms. $\endgroup$
    – Yuval Filmus
    Commented Apr 30, 2019 at 16:21

1 Answer 1

Reset to default
9
$\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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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