Home Research Teaching Contact
Research on the Approximability of CSPs

Overview:
In constraint satisfaction problems (CSPs), we are given a set of constraints and we are asked to satisfy as many of them as possible. A natural question about CSPs is as follows. For a given type of CSP, what is the best approximation ratio that we can guarantee between the number of constraints satisfied by our solution (which we find with a probabilistic polynomial time algorithm) and the maximum possible number of constraints that can be satisfied?

Two central CSPs for which this question has been resolved (assuming the unique games conjecture or at least that unique games is hard) are 3-SAT and MAX CUT. For 3-SAT, guessing a random assignment satisfies 7/8 of the constraints in expectation and Johan HÃ¥stad's 3-bit PCP (probabilistically checkable proof) shows that it is NP-hard to obtain a ratio which is better than 7/8. For MAX CUT, the Goemans-Williamson algorithm gives a .878 approximation ratio and the paper "Optimal
inapproximability results for max-cut and other 2-variable CSPs?" by Subhash Khot, Guy Kindler, Elchannan Mossel, and Ryan O'Donnell shows that this algorithm is optimal (assuming that unique games is hard) .

For general CSPs, Prasad Raghavendra showed in his breakthrough paper "Optimal Algorithms and Inapproximability Results for Every CSP?" that (assuming unique games is hard) the optimal polynomial-time algorithm for any type of CSP is to use a standard semidefinite program (SDP) followed by a rounding scheme which rounds the output of the SDP into an actual solution. However, determining which rounding scheme is optimal may be extremely hard. In fact, it is not even known to be decidable! For this reason, there is still much that is unknown about the approximability of CSPs.

Papers: