# MAX 10-SAT Algorithm

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 :(

• is there any 99.9% approximation algorithm out there? – seteropere May 15 '13 at 8:49
• 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. – Juho May 15 '13 at 22:05

## 2 Answers

Try choosing a random assignment.

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

• 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. – D.W. Apr 22 '15 at 0:08
• MAX-CUT and MAX-SAT have very similar approximation techniques so I think this answer is fine. I've edited to mention both. – David Richerby Apr 22 '15 at 7:20