# 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