Approximate Constraint Satisfaction Requires Large LP Relaxations

Author

Siu On Chan ; Lee, J. ; Raghavendra, Prasad ; Steurer, David

Author_Institution

Microsoft Research New England, Cambridge, MA, USA

fYear

2013

fDate

26-29 Oct. 2013

Firstpage

350

Lastpage

359

Abstract

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for MAX CUT has an integrality gap of 1/2 and any such linear program for MAX 3-SAT has an integrality gap of 7/8.

Keywords

computability; computational complexity; constraint satisfaction problems; graph theory; linear programming; LP relaxation; MAX 3-SAT; MAX CUT; Sherali-Adams hierarchy; approximate constraint satisfaction problem; linear programming relaxations; polynomial-sized linear programs; superpolynomial lower bounds; Approximation methods; Complexity theory; Entropy; Linear programming; Optimized production technology; Polynomials; Vectors; LP hierarchies; approximation complexity; constraint satisfaction problems; extended formulations; linear programming; lower bounds;

fLanguage

English

Publisher

ieee

Conference_Titel

Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on

Conference_Location

Berkeley, CA

ISSN

0272-5428

Type

conf

DOI

10.1109/FOCS.2013.45

Filename

6686171