Exponential Lower Bounds for Polytopes in Combinatorial Optimization
arXiv:1111.0837
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.
arXiv comment19 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 (9)
- Non-locality and Communication Complexity
- Symmetry Matters for Sizes of Extended Formulations
- 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
- Extended formulations, non-negative factorizations and randomized communication protocols
- Combinatorial Bounds on Nonnegative Rank and Extended Formulations
- Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results
- Correlation/Communication complexity of generating bipartite states
Cited by in corpus (6)
- Polytopes of Minimum Positive Semidefinite Rank
- Deciding polyhedrality of spectrahedra
- 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"