TY - GEN

T1 - Approximating CSPs using LP relaxation

AU - Khot, Subhash

AU - Saket, Rishi

N1 - Funding Information:
Subhash Khot—Research supported by NSF grants CCF 1422159, 1061938, 0832795 and Simons Collaboration on Algorithms and Geometry grant.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - 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(k3 ・ log L) of the optimal approximation factor. In particular we prove the following hardness result: let I be a k-ary CSP on label set [L] with constraints from a constraint class C, such that it is a (c, s)-integrality gap for the standard LP relaxation. Then, given an instance H with constraints from C, it is NP-hard to decide whether, (Formula Presented.) assuming the Unique Games Conjecture. We also show the existence of an efficient LP rounding algorithm Round such that given an instance H from a permutation invariant constraint class C which is a (c, s)-rounding gap for Round, it is NP-hard to decide whether, (Formula Presented.) assuming the Unique Games Conjecture.

AB - 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(k3 ・ log L) of the optimal approximation factor. In particular we prove the following hardness result: let I be a k-ary CSP on label set [L] with constraints from a constraint class C, such that it is a (c, s)-integrality gap for the standard LP relaxation. Then, given an instance H with constraints from C, it is NP-hard to decide whether, (Formula Presented.) assuming the Unique Games Conjecture. We also show the existence of an efficient LP rounding algorithm Round such that given an instance H from a permutation invariant constraint class C which is a (c, s)-rounding gap for Round, it is NP-hard to decide whether, (Formula Presented.) assuming the Unique Games Conjecture.

UR - http://www.scopus.com/inward/record.url?scp=84950124605&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84950124605&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-47672-7_67

DO - 10.1007/978-3-662-47672-7_67

M3 - Conference contribution

AN - SCOPUS:84950124605

SN - 9783662476710

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 822

EP - 833

BT - Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings

A2 - Halldorsson, Magnus M.

A2 - Kobayashi, Naoki

A2 - Speckmann, Bettina

A2 - Iwama, Kazuo

PB - Springer Verlag

T2 - 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015

Y2 - 6 July 2015 through 10 July 2015

ER -