Approximate Constraint Satisfaction Requires Large LP Relaxations

New York area theory day, TCS+ online seminar series, EPFL theory colloquium.

PDF

VIDEO

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, general polynomial-sized linear programs are exactly as powerful as those arising from the Sherali–Adams hierarchy.

Concrete consequences are that polynomial-sized linear programming relaxation cannot achieve better than ½-approximations for MAX-CUT, ⅞-approximations for MAX-3SAT, or ¾-approximations for MAX-2SAT.

Our techniques bring together two formerly disparate lines of research. On the one hand, there has been a recent sequence of exciting lower bounds on the size of extended formulations for various polytopes that arise in combinatorial optimization. At the same time, researchers have extensively studied the power of specific LP relaxations, e.g., from the Sherali–Adams hierarchy, for approximating NP-hard problems.

Joint work with Siu On Chan, James R. Lee, and Prasad Raghavendra.