Regular Matroids Have Polynomial Extension Complexity
- 1 February 2022
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 47 (1) , 540-559
Abstract
We prove that the extension complexity of the independence polytope of every regular matroid on n elements is O(n6). Past results of Wong and Martin on extended formulations of the spanning tree po...Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Some 0/1 polytopes need exponential size extended formulationsMathematical Programming, 2012
- Symmetry Matters for Sizes of Extended FormulationsSIAM Journal on Discrete Mathematics, 2012
- Extended formulations in combinatorial optimization4OR, 2010
- On the cut polyhedronDiscrete Mathematics, 2004
- A linear‐size zero—one programming model for the minimum spanning tree problem in planar graphsNetworks, 2001
- The intractability of computing the minimum distance of a codeIEEE Transactions on Information Theory, 1997
- Expressing combinatorial optimization problems by Linear ProgramsJournal of Computer and System Sciences, 1991
- Using separation algorithms to generate mixed integer model reformulationsOperations Research Letters, 1991
- Decomposition of regular matroidsJournal of Combinatorial Theory, Series B, 1980
- Disjunctive Programming1979