Title : Optimal Algorithms and Inapproximability Results for every CSP?
Speaker: Prasad Raghavendra, Univ. of Washington.
ABSTRACT :
Semidefinite Programming(SDP) is one of the strongest algorithmic techniques used in the design of
approximation algorithms. In recent years, Unique Games Conjecture(UGC) has proved to be intimately
connected to the limitations of Semidefinite Programming.
Making this connection precise, we show the following result :
If UGC is true, then for every constraint satisfaction problem(CSP) the best approximation ratio is
given by certain simple SDP. Specifically, we show a generic conversion from SDP integrality gap
instances to UGC hardness results. This result holds both for maximization and minimization
problems over arbitrary finite domains.
Using this connection between integrality gaps and hardness results we
obtain a generic polynomial-time algorithm for all CSPs. Assuming the Unique Games Conjecture, this
algorithm achieves the optimal approximation ratio for every CSP.
Unconditionally, for all 2-CSPs the algorithm achieves an approximation ratio equal to the
integrality gap of the natural SDP. Thus the algorithm achieves at least as good an approximation
ratio as the best known algorithms for several problems like MaxCut, Max2SAT and Unique Games.