On the combinatorial lower bound for the extension complexity of the spanning tree polytope

DOI10.1016/j.orl.2018.03.008OpenAlexW2586559425WikidataQ130034043 ScholiaQ130034043MaRDI 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

zbMATH Keywords

communication complexityextension complexityspanning tree polytope

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items (3)

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes ⋮ Extended formulations for matroid polytopes through randomized protocols

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

This page was built for publication: On the combinatorial lower bound for the extension complexity of the spanning tree polytope