How to round any CSP

with Prasad Raghavendra. FOCS 2009.

abstract

A large number of interesting combinatorial optimization problems like Max Cut, Max k-Sat, and Unique Games fall under the class of constraint satisfaction problems (CSPs).

Recent work by Raghavendra (STOC 2008) identifies a semidefinite programming (SDP) relaxation that yields the optimal approximation ratio for every CSP, under the Unique Games Conjecture (UGC). Very recently (FOCS 2009), the authors also showed unconditionally that the integrality gap of this basic SDP relaxation cannot be reduced by adding large classes of valid inequalities (e.g., in the fashion of Sherali–Adams LP hierarchies).

In this work, we present an efficient rounding scheme that achieves the integrality gap of this basic SDP relaxation for every CSP (and it also achieves the gap of much stronger SDP relaxations).

The rounding algorithm in this paper can be summarized succinctly as follows: Reduce the dimension of SDP solution by random projection, discretize the projected vectors, and solve the resulting CSP instance by brute force! Even the proof is simple in that it avoids the use of the machinery from unique games reductions such as dictatorship tests, Fourier analysis or the invariance principle.

A common theme of this paper and the subsequent paper in the same conference is a robustness lemma for SDP relaxations which asserts that approximately feasible solutions can be made feasible by “smoothing” without changing the objective value significantly.

keywords

semidefinite programming
constraint satisfaction problems
approximation algorithms