The matching polytope has exponential extension complexity

DOI10.1145/2591796.2591834MaRDI QIDQ6829582zbMATH OpenFDO

Authors Thomas Rothvoß

Publication date 26 June 2015

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

zbMATH Keywords

combinatorial optimizationpolytopeslinear programming relaxations

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

This page was built for publication: The matching polytope has exponential extension complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6829582)