On the combinatorial lower bound for the extension complexity of the spanning tree polytope
From MaRDI portal
Publication:2417165
DOI10.1016/j.orl.2018.03.008MaRDI QIDQ2417165
Kaveh Khoshkhah, Dirk Oliver Theis
Publication date: 11 June 2019
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.01424
90-XX: Operations research, mathematical programming
Cites Work
- Unnamed Item
- Extended formulations, nonnegative factorizations, and randomized communication protocols
- Using separation algorithms to generate mixed integer model reformulations
- Expressing combinatorial optimization problems by linear programs
- Fooling sets and the spanning tree polytope
- Combinatorial bounds on nonnegative rank and extended formulations
- The (minimum) rank of typical fooling-set matrices
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- The Matching Polytope has Exponential Extension Complexity
- Symmetry Matters for Sizes of Extended Formulations