Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
From MaRDI portal
Publication:2670454
DOI10.1016/j.orl.2021.11.006OpenAlexW3211971493MaRDI QIDQ2670454
Publication date: 11 March 2022
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1911.01541
extension complexityslack matrixgraphic zonotopespanning tree polytopecompletion time polytopehyperplane separation bound
Cites Work
- Unnamed Item
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Smaller extended formulations for the spanning tree polytope of bounded-genus graphs
- Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
- Extended formulations for polygons
- Smallest compact formulation for the permutahedron
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Extended formulations, nonnegative factorizations, and randomized communication protocols
- Faces of generalized permutohedra
- Using separation algorithms to generate mixed integer model reformulations
- Expressing combinatorial optimization problems by linear programs
- Combinatorial bounds on nonnegative rank and extended formulations
- Subgraph polytopes and independence polytopes of count matroids
- Structure of a simple scheduling polyhedron
- Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
- A short proof that the extension complexity of the correlation polytope grows exponentially
- On the combinatorial lower bound for the extension complexity of the spanning tree polytope
- Some \(0/1\) polytopes need exponential size extended formulations
- Submodular functions and optimization.
- A linear-size zero?one programming model for the minimum spanning tree problem in planar graphs
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- The Matching Polytope has Exponential Extension Complexity
- Symmetry Matters for Sizes of Extended Formulations
- Constructing Extended Formulations from Reflection Relations
- Matroids and the greedy algorithm
- Extended formulations in combinatorial optimization
