Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CSPS:
Reports tagged with CSPs:
TR16-116 | 26th July 2016
Subhash Khot, Rishi Saket

#### Approximating CSPs using LP Relaxation

This paper studies how well the standard LP relaxation approximates a $k$-ary constraint satisfaction problem (CSP) on label set $[L]$. We show that, assuming the Unique Games Conjecture, it achieves an approximation within $O(k^3\cdot \log L)$ of the optimal approximation factor. In particular we prove the following hardness result: let ... more >>>

ISSN 1433-8092 | Imprint