Fast SDP algorithms for constraint satisfaction problems

SODA 2010.

abstract

The class of constraint satisfactions problems (CSPs) contains many fundamental combinatorial optimization problems such as Max Cut and Max 3-SAT.

Recently, Raghavendra (STOC'08) showed that a certain semidefinite programming relaxation gives the best possible approximation for any CSP, assuming Khot's Unique Games Conjecture. Raghavendra and Steurer (FOCS'09) show 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 approximate solution to this relaxation in near-linear time. Combining this algorithm with a rounding scheme of Raghavendra and Steurer (FOCS'09) yields 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.

Our algorithm is based a framework of Arora and Kale (STOC'07) for solving semidefinite programs. In this framework, the crucial step is to design an efficient width-bounded separation oracle. We show how to implement this oracle by solving a sequence of local linear programs. We also generalize the framework of Arora and Kale in order to deal with irregular instances more efficiently.

keywords

semidefinite programming
constraint satisfaction problems
approximation algorithms
fast algorithm