Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR16-116 | 26th July 2016 19:19

Approximating CSPs using LP Relaxation

TR16-116
Authors: Subhash Khot, Rishi Saket
Publication: 31st July 2016 10:19
Keywords:

Abstract:

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 ${\cal I}$ be a $k$-ary CSP on label set $[L]$ with constraints from a ${\it constraint\ class}$ ${\cal C}$, such that it is a $(c,s)$-integrality gap for the standard LP relaxation. Then, given an instance ${\cal H}$ with constraints from ${\cal C}$, it is NP-hard to decide whether,
$$\textrm{opt}({\cal H}) \geq \Omega\left(\frac{c}{k^3\log L}\right),\ \ \textrm{ or }\ \ \textrm{opt}({\cal H}) \leq 4\cdot s,$$
assuming the Unique Games Conjecture. We also show the existence of an efficient LP rounding algorithm ${\it Round}$ such that a lower bound for it can be translated into a similar (but weaker) hardness result. In particular, if there is an instance from a ${\it permutation\ invariant}$ constraint class ${\cal C}$ which is a $(c,s)$-${\it rounding\ gap}$ for ${\it Round}$, then given an instance ${\cal H}$ with constraints from ${\cal C}$, it is NP-hard to decide whether,
$$\textrm{opt}({\cal H}) \geq \Omega \left(\frac{c}{k^3\log L}\right),\ \ \textrm{ or }\ \ \textrm{opt}({\cal H}) \leq O\left((\log L)^k\right)\cdot s,$$
assuming the Unique Games Conjecture.

An extended abstract of this paper appeared in the Proceedings of The 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015).

ISSN 1433-8092 | Imprint