TY - GEN
T1 - Approximating CSPs using LP relaxation
AU - Khot, Subhash
AU - Saket, Rishi
N1 - 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 -