Approximate Constraint Satisfaction Requires Large LP Relaxations
Authors:
- Siu On ChanSCSiu On Chan
- James R. LeeJLJames R. Lee
- Prasad RaghavendraPRPrasad Raghavendra
- David SteurerDSDavid Steurer
- 1 October 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 350-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
All Related Versions
This publication has 15 references indexed in Scilit:
- Approximation Limits of Linear Programs (Beyond Hierarchies)2012
- Linear vs. semidefinite extended formulations2012
- The Design of Approximation Algorithms2011
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 ProgrammingMathematics of Operations Research, 2003
- Some optimal inapproximability resultsJournal of the ACM, 2001
- Concentration1998
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- Expressing combinatorial optimization problems by Linear ProgramsJournal of Computer and System Sciences, 1991
- Cones of Matrices and Set-Functions and 0–1 OptimizationSIAM Journal on Optimization, 1991
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming ProblemsSIAM Journal on Discrete Mathematics, 1990