Fooling sets and the spanning tree polytope

DOI10.1016/j.ipl.2017.05.009zbMath1434.90171arXiv1701.00350OpenAlexW2569968971MaRDI QIDQ1705643

Dirk Oliver Theis, Kaveh Khoshkhah

Publication date: 16 March 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1701.00350

zbMATH Keywords

lower boundsextended formulationspolyhedral combinatorial optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (3)

The rectangle covering number of random Boolean matrices ⋮ On the combinatorial lower bound for the extension complexity of the spanning tree polytope ⋮ Fooling sets and the spanning tree polytope

Cites Work

• Smaller extended formulations for the spanning tree polytope of bounded-genus graphs
• Extended formulations, nonnegative factorizations, and randomized communication protocols
• Using separation algorithms to generate mixed integer model reformulations
• A comparison of two lower-bound methods for communication complexity
• Fooling sets and the spanning tree polytope
• Combinatorial bounds on nonnegative rank and extended formulations
• Fooling-sets and rank
• The (minimum) rank of typical fooling-set matrices
• Communication Complexity
• Symmetry Matters for Sizes of Extended Formulations
• Fooling-sets and rank in nonzero characteristic (extended abstract)
• Extended formulations in combinatorial optimization

This page was built for publication: Fooling sets and the spanning tree polytope