The Matching Polytope has Exponential Extension Complexity
Author:
Top Cited Papers
Open Access
- 28 September 2017
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 64 (6) , 1-19
Abstract
A popular method in combinatorial optimization is to express polytopes P , which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. After two decades of standstill, recent years have brought amazing progress in showing lower bounds for the so-called extension complexity , which for a polytope P denotes the smallest number of inequalities necessary to describe a higher-dimensional polytope Q that can be linearly projected on P . However, the central question in this field remained wide open: can the perfect matching polytope be written as an LP with polynomially many constraints? We answer this question negatively. In fact, the extension complexity of the perfect matching polytope in a complete n -node graph is 2 Ω ( n ) . By a known reduction, this also improves the lower bound on the extension complexity for the TSP polytope from 2 Ω (√ n ) to 2 Ω ( n ) .Keywords
All Related Versions
Funding Information
- NSF (1115849)
- ONR (N00014-11-1-0053)
This publication has 24 references indexed in Scilit:
- Combinatorial bounds on nonnegative rank and extended formulationsDiscrete Mathematics, 2013
- Extended Formulations for PolygonsDiscrete & Computational Geometry, 2012
- On the distributional complexity of disjointness2005
- A compact linear program for testing optimality of perfect matchingsOperations Research Letters, 2003
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- On cuts and matchings in planar graphsMathematical Programming, 1993
- Expressing combinatorial optimization problems by Linear ProgramsJournal of Computer and System Sciences, 1991
- Compact systems for T-join and perfect matching polyhedra of graphs with bounded genusOperations Research Letters, 1991
- Using separation algorithms to generate mixed integer model reformulationsOperations Research Letters, 1991
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization ProblemsSIAM Journal on Algebraic Discrete Methods, 1985