A 7/8-Approximation Algorithm for MAX 3SAT?

We describe a randomized approximation algorithm which takes an instance of MAX 3SAT as input. If the instance-a collection of clauses each of length at most three-is satisfiable, then the expected weight of the assignment found is at least 7/8 of optimal. We provide strong evidence (but not a proof) that the algorithm performs equally well on arbitrary MAX 3SAT instances. Our algorithm uses semidefinite programming and may be seen as a sequel to the MAX CUT algorithm of Goemans and Williamson (1995) and the MAX 2SAT algorithm of Feige and Goemans (1995). Though the algorithm itself is fairly simple, its analysis is quite complicated as it involves the computation of volumes of spherical tetrahedra. Hastad has recently shown that, assuming P/spl ne/NP, no polynomial-time algorithm for MAX 3SAT can achieve a performance ratio exceeding 7/8, even when restricted to satisfiable instances of the problem. Our algorithm is therefore optimal in this sense. We also describe a method of obtaining direct semidefinite relaxations of any constraint satisfaction problem of the form MAX CSP(F), where F is a finite family of Boolean functions. Our relaxations are the strongest possible within a natural class of semidefinite relaxations.

Authors

• Howard J. Karloff
• Uri Zwick

Keywords

• Approximation algorithms
• Polynomials
• Boolean functions
• Computer science
• Linear programming
• Estimation Algorithm
• Problem Instances
• Polynomial-time Algorithm
• Constraint Satisfaction Problem
• Boolean Function
• Semidefinite Relaxation
• Systematic Search
• Unit Vector
• Dihedral Angle
• Value Of Solution
• Mathematica
• Unit Sphere
• Triangle Inequality
• Semidefinite Programming
• Polytope
• Representative Algorithms
• Formula Volume