Optimal algorithms and inapproximability results for every CSP?
Prasad Raghavendra · 2008
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.