Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint

An instance of MAX 3CSP is a collection of m clauses of the form f i (z i1 ; z i2 ; z i3 ), where the z ij s are literals, or constants, from the set f0; 1; x 1 ; : : : ; xn ; x 1 ; : : : ; xng, and the f i s are arbitrary Boolean functions depending on (at most) three variables. Each clause has a non-negative weight w i associated with it. A solution to the instance is an assignment of 0-1 values to the variables x 1 ; : : : ; xn that maximizes P n i=1 w i f i (z i1 ; z i2 ; z i3 ), the total weight of the satisfied clauses. The MAX 3CSP problem is clearly a generalization of the MAX 3SAT problem. (In an instance of the MAX 3SAT problem f i (z i1 ; z i2 ; z i3 ) = z i1 z i2 z i3 for every i.) Karloff and Zwick have recently obtained a 8 -approximation algorithm for MAX 3SAT. Their algorithm is based on a new semidefinite relaxation of the problem. Hastad showed that no polynomial time algorithm can achieve a better performance ratio, unless P=NP. Here we use similar techniques to obtain a -approximation algorithm for MAX 3CSP. The performance ratio of this algorithm is also optimal, as follows again from the work of Hastad. We also obtain better performance ratios for several special cases of the problem. Our results include: 2 -approximation algorithm for MAX 3AND, the problem in which each clause is of the form z i1 z i2 z i3 . This result is optimal and it implies the result for MAX 3CSP.