The matching polytope has exponential extension complexity

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).

• Publication year

  2013

• Venue

  Symposium on the Theory of Computing

• Publication date

  2013-11-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2591796.2591834arXiv 1311.2369
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Smallest compact formulation for the permutahedron

  2015cited by this paper
• The matching polytope does not admit fully-polynomial size relaxation schemes

  2014cited by this paper
• Lower Bounds on the Size of Semidefinite Programming Relaxations

  2014cited by this paper
• An information complexity approach to extended formulations

  2013cited by this paper
• Common Information and Unique Disjointness

  2013cited by this paper
• Approximate Constraint Satisfaction Requires Large LP Relaxations

  2013cited by this paper
• A note on the extension complexity of the knapsack polytope

  2013cited by this paper
• On the extension complexity of combinatorial polytopes

  2013cited by this paper
• On the existence of 0/1 polytopes with high semidefinite extension complexity

  2013cited by this paper
• Symmetry Matters for Sizes of Extended Formulations

  2012cited by this paper
• Approximation Limits of Linear Programs (Beyond Hierarchies)

  2012cited by this paper
• Combinatorial bounds on nonnegative rank and extended formulations

  2011cited by this paper
• Extended formulations, nonnegative factorizations, and randomized communication protocols

  2011cited by this paper
• Extended Formulations for Polygons

  2011cited by this paper
• Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

  2011influential reference
• Some 0/1 polytopes need exponential size extended formulations

  2011cited by this paper
• Probability and Computing: Randomized Algorithms and Probabilistic Analysis

  2005cited by this paper
• A compact linear program for testing optimality of perfect matchings

  2003cited by this paper
• Combinatorial optimization. Polyhedra and efficiency.

  2003cited by this paper
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995cited by this paper
• On cuts and matchings in planar graphs

  1993cited by this paper
• Combinatorial Optimization

  1992cited by this paper
• Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus

  1991cited by this paper
• Expressing combinatorial optimization problems by linear programs

  1991influential reference
• Using separation algorithms to generate mixed integer model reformulations

  1991cited by this paper
• On the Distributional Complexity of Disjointness

  1990influential reference
• A personal communication

  1989cited by this paper
• Disjunctive programming and a hierarchy of relaxations for discrete optimization problems

  1985cited by this paper
• Odd Minimum Cut-Sets and b-Matchings

  1982cited by this paper
• Matroids and the greedy algorithm

  1971cited by this paper
• Maximum matching and a polyhedron with 0,1-vertices

  1965cited by this paper

• Min-Max Connected Multiway Cut

  2026cites this paper
• Spectral Ghost in Representation Learning: from Component Analysis to Self-Supervised Learning

  2026cites this paper
• Equiprojective polytopes in higher dimension

  2026cites this paper
• Improved Algorithms and Novel Applications of the FrankWolfe.jl Library

  2025cites this paper
• Vanishing of Schubert coefficients is in AM ∩ coAM assuming the GRH

  2025cites this paper
• Normalizations of factorizations over convex cones and their effects on extension complexity

  2025cites this paper
• Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width

  2025cites this paper
• Flexible block-iterative analysis for the Frank-Wolfe algorithm

  2024cites this paper
• Matroid Products via Submodular Coupling

  2024cites this paper
• Neural Networks and (Virtual) Extended Formulations

  2024influential citation
• Beyond hypergraph acyclicity: limits of tractability for pseudo-Boolean optimization

  2024cites this paper
• Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding

  2023cites this paper
• The Frank-Wolfe Algorithm: A Short Introduction

  2023cites this paper
• Primal Separation and Approximation for the {0, 1/2}-closure

  2023cites this paper
• The Mathematics of L\'aszl\'o Lov\'asz

  2023cites this paper
• Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity

  2023cites this paper
• Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack

  2023cites this paper
• PAC Reinforcement Learning for Predictive State Representations

  2022cites this paper
• Individual and cooperative portfolio optimization as linear program

  2022cites this paper
• Perfect Matching in Random Graphs is as Hard as Tseitin

  2022cites this paper
• On Semi-Algebraic Proofs and Algorithms

  2022cites this paper
• The role of rationality in integer-programming relaxations

  2022cites this paper
• Proofs, Circuits, and Communication

  2022cites this paper
• The Exact Bipartite Matching Polytope Has Exponential Extension Complexity

  2022influential citation
• Guest Column

  2022cites this paper
• Accelerated Gradient Descent

  2021cites this paper
• Shadows of newton polytopes

  2021cites this paper
• Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions

  2021cites this paper
• Extended formulations for matroid polytopes through randomized protocols

  2021cites this paper
• On Extended Formulations For Parameterized Steiner Trees

  2021cites this paper
• Ellipsoid Method for Linear Programming

  2021cites this paper
• Convexity

  2021cites this paper
• Variants of Interior Point Method and Self-Concordance

  2021cites this paper
• Scalable Frank-Wolfe on Generalized Self-Concordant Functions via Simple Steps

  2021cites this paper
• ReLU neural networks of polynomial size for exact maximum flow computation

  2021cites this paper
• Duality and Optimality

  2021cites this paper
• Bridging Continuous and Discrete Optimization

  2021cites this paper
• Complex psd-minimal polytopes in dimensions two and three

  2021cites this paper
• Lifts for Voronoi Cells of Lattices

  2021cites this paper
• Learning in Combinatorial Optimization: What and How to Explore

  2020influential citation
• Extension Complexity of Polytopes

  2020cites this paper
• A geometric lower bound on the extension complexity of polytopes based on the f-vector

  2020cites this paper
• Cuts in Undirected Graphs. I

  2020cites this paper
• On ε-sensitive monotone computations.

  2020cites this paper
• Extension Complexity via Lifting LP Hierarchy Lower Bounds

  2020cites this paper
• Extension complexity of low-dimensional polytopes

  2020cites this paper
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs

  2020cites this paper
• On the Complexity of Some Facet-Defining Inequalities of the QAP-polytope

  2020cites this paper
• Extended formulations of lower-truncated transversal polymatroids

  2020cites this paper
• Circuits and Proofs

  2020cites this paper
• Index

  2020cites this paper
• Matching Polytope and Totally Dual Integrality

  2020cites this paper
• Deterministic Protocols

  2020cites this paper
• Bibliography

  2020cites this paper
• Cuts in Undirected Graphs. II

  2020cites this paper
• Randomized Protocols

  2020cites this paper
• Memory Size

  2020cites this paper
• References

  2020cites this paper
• Communication Complexity

  2020cites this paper
• Compressing Communication

  2020cites this paper
• Discrepancy

  2020cites this paper
• Introduction

  2020cites this paper
• Numbers on Foreheads

  2020cites this paper
• Preface

  2020cites this paper
• On the complexity of computing a random Boolean function over the reals

  2020cites this paper
• Sparktope: linear programs from algorithms

  2020influential citation
• Tropical lower bound for extended formulations. II. Deficiency graphs of matrices

  2019cites this paper
• On the Power of Symmetric Linear Programs

  2019cites this paper
• An Integral Linear Programming Relaxation for Parameterized Steiner Trees (cid:63)

  2019cites this paper
• Representations of Monotone Boolean Functions by Linear Programs

  2019influential citation
• Symmetric Computation

  2019cites this paper
• Mathematics and Computation

  2019cites this paper
• Complexity-Theoretic Barriers in Economics

  2019cites this paper
• Limitations of the Hyperplane Separation Technique for Bounding the Extension Complexity of Polytopes

  2019influential citation
• Extended Formulation Lower Bounds for Refuting Random CSPs

  2019cites this paper
• Alternating conditional gradient method for convex feasibility problems

  2019cites this paper
• Locally Accelerated Conditional Gradients

  2019cites this paper
• Regular matroids have polynomial extension complexity

  2019cites this paper
• Fe b 20 16 Computing approximate PSD factorizations

  2018cites this paper
• Strong reductions for extended formulations

  2018cites this paper
• Extended formulations from communication protocols in output-efficient time

  2018cites this paper
• On polyhedral approximations of the positive semidefinite cone

  2018cites this paper
• The Ramping Polytope and Cut Generation for the Unit Commitment Problem

  2018cites this paper
• Output-sensitive complexity of multiobjective combinatorial optimization with an application to the multiobjective shortest path problem

  2018cites this paper
• Extended Formulation Lower Bounds for Combinatorial Optimization

  2018cites this paper
• Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

  2018cites this paper
• The slack realization space of a matroid

  2018cites this paper
• O C ] 1 8 A pr 2 01 8 Compact linear programs for 2 SAT

  2018cites this paper
• Gradient Descent

  2018cites this paper
• Computing the nucleolus of weighted cooperative matching games in polynomial time

  2018cites this paper
• Data-Driven Learning Models with Applications to Retail Operations

  2018cites this paper
• Lower Bounds for Interactive Compression and Linear Programs

  2018cites this paper
• Limits of Treewidth-based tractability in Optimization

  2018cites this paper
• New limits of treewidth-based tractability in optimization

  2018cites this paper
• On some problems related to 2-level polytopes

  2018cites this paper
• Disjunctive Programming and Extended Formulations

  2018cites this paper
• Cutting Plane and Ellipsoid Methods for Linear Programming

  2018cites this paper
• Extended Formulations for Radial Cones

  2018influential citation
• Matchings and Representation Theory

  2018cites this paper
• A reduction framework for approximate extended formulations and a faster algorithm for convex optimization

  2017cites this paper