Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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