3
$\begingroup$

The MAX k-SAT problem is:

“Given a set of clauses C1,…,Ck, each of length k, over a set of variables x1,…,xn, find a truth assignment that satisfies as many of the clauses as possible.”

I'm trying for find a randomized 0.999-approximation algorithm for the MAX 10-SAT problem. Help :(

$\endgroup$
  • $\begingroup$ is there any 99.9% approximation algorithm out there? $\endgroup$ – seteropere May 15 '13 at 8:49
  • $\begingroup$ Note that every clause has exactly 10 variables. Choose a random assignment. Then, use linearity of expectation and remember you are dealing with 0-1 random variables. The same analysis works for other values of $k$ too. $\endgroup$ – Juho May 15 '13 at 22:05
7
$\begingroup$

Try choosing a random assignment.

$\endgroup$
-1
$\begingroup$

Have a look at chapter 5 of this book (available for free):

The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys

The book discusses several randomized algorithms with different performance guarantees for MAX-SAT and MAX CUT (for details of the algorithms, you should have a look at the references in the book).

$\endgroup$
  • 1
    $\begingroup$ The question asks about MAX 10-SAT, but your answer talks about MAX-CUT. The connection is not clear. You might want to edit your answer, or delete it if you misunderstood the question. $\endgroup$ – D.W. Apr 22 '15 at 0:08
  • 1
    $\begingroup$ MAX-CUT and MAX-SAT have very similar approximation techniques so I think this answer is fine. I've edited to mention both. $\endgroup$ – David Richerby Apr 22 '15 at 7:20

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.