Approximate Constraint Satisfaction Requires Large LP Relaxations

Authors:
  • SCSiu On Chan
    Siu On Chan
  • JLJames R. Lee
    James R. Lee
  • PRPrasad Raghavendra
    Prasad Raghavendra
  • DSDavid Steurer
    David Steurer

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.

This publication has 15 references indexed in Scilit: