Approximate Constraint Satisfaction Requires Large LP Relaxations
Siu On Chan
, Microsoft Research New England
Date: Wednesday, October 16, 2013
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Contact: Ilya Razenshteyn, email@example.com
Relevant URL: http://www.ilyaraz.org/acseminar/
Speaker URL: None
TALK: 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.
Joint work with James Lee, Prasad Raghavendra, and David Steurer.
Created by Ilya Razenshteyn at Monday, October 14, 2013 at 9:47 PM.