Exponential Lower Bounds for Polytopes in Combinatorial Optimization

Abstract

We solve a 20-year old problem posed by Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

19 pages, 4 figures. This version of the paper will appear in the Journal of the ACM. The earlier conference version in STOC'12 had the title "Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds"

References in corpus (5)

• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Some 0/1 polytopes need exponential size extended formulations
• Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix
• Combinatorial Bounds on Nonnegative Rank and Extended Formulations
• Correlation/Communication complexity of generating bipartite states

Cited by in corpus (5)

• Polytopes of Minimum Positive Semidefinite Rank
• Approximations of convex bodies by polytopes and by projections of spectrahedra
• An algebraic approach to symmetric extended formulations
• Limits to the scope of applicability of extended formulations for LP models of combinatorial optimization problems: A summary
• On Limits to the Scope of the Extended Formulations "Barriers"