MAX 10-SAT Algorithm

Question

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

Answer 1

Try choosing a random assignment.

Answer 2

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