Fast SDP Algorithms for Constraint Satisfaction Problems

The class of constraint satisfactions problems (CSPs) captures many fundamental combinatorial optimization problems such as M ax C ut, M ax q -C ut, U nique G ames, and M ax k -S at. Recently, Raghavendra (STOC'08) identified a simple semidefinite programming relaxation that gives the best possible approximation for any CSP, assuming the Unique Games Conjecture. Raghavendra and Steurer (FOCS'09) showed that, independent of the truth of the Unique Games Conjecture, the integrality gap of this relaxation cannot be improved even by adding a large class of valid inequalities. We present an algorithm that finds an approximately optimal solution to this relaxation in near-linear time. Combining this algorithm with a rounding scheme of Raghavendra and Steurer (FOCS'09) leads to an approximation algorithm for any CSP that runs in near-linear time and has an approximation guarantee that matches the integrality gap, which is optimal assuming the Unique Games Conjecture.

Authors

• David Steurer

Keywords

No keywords are indexed for this paper.