TR16-116 Authors: Subhash Khot, Rishi Saket

Publication: 31st July 2016 10:19

Downloads: 1173

Keywords:

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).