The Matching Polytope has Exponential Extension Complexity

DOI10.1145/3127497zbMath1426.90255arXiv1311.2369WikidataQ115522540 ScholiaQ115522540MaRDI QIDQ4640350

Thomas Rothvoß

Publication date: 17 May 2018

Published in: Journal of the ACM, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.2369

zbMATH Keywords

linear programming; polytopes; combinatorial optimization; matching; linear programming relaxations; extension complexity

Mathematics Subject Classification ID

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90C05: Linear programming

90C27: Combinatorial optimization

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

Uses Software

• SuLQ