Approximate Constraint Satisfaction Requires Large LP Relaxations

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.

Authors

• Siu On Chan
• James R. Lee
• Prasad Raghavendra
• David Steurer

Keywords

• Approximation methods
• Linear programming
• Vectors
• Entropy
• Complexity theory
• Polynomials
• Optimized production technology
• Constraint Satisfaction
• Lower Bound
• Constraint Satisfaction Problem
• Linear Relaxation
• Max-Cut
• Linear Programming Relaxation
• Optimization Problem
• Function Tests
• High Entropy
• Linear Inequalities
• Nonnegative Function
• Fourier Coefficients
• Vertex Cover
• Functional Sense
• Fourier Basis
• extended formulations
• lower bounds
• LP hierarchies
• constraint satisfaction problems
• approximation complexity