Approximate constraint satisfaction requires large LP relaxations

with Siu On Chan, James R. Lee, Prasad Raghavendra. FOCS 2013.

PDF

Invited to FOCS 2013 special issue, Accepted to JACM

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 MAXCUT has an integrality gap of 12\frac12 and any such linear program for MAX 3-SAT has an integrality gap of 78\frac78.

keywords

  • strong relaxations
  • lower bounds
  • linear programming
  • constraint satisfaction problems