Fooling sets and the spanning tree polytope

DOI10.1016/J.IPL.2017.05.009MaRDI QIDQ1705643zbMATH OpenOpenAlexFDO

Authors Kaveh Khoshkhah, Dirk Oliver Theis

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

extended formulationslower boundspolyhedral combinatorial optimization

Mathematics Subject Classification ID

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

Abstract: In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with $n$ nodes. The best known lower bound is $Omega(n^2)$, the best known upper bound is $O(n^3)$. In this note we show that the venerable fooling set method cannot be used to improve the lower bound: every fooling set for the Spanning Tree polytope has size $O(n^2)$.

Recommendations

• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Smaller extended formulations for the spanning tree polytope of bounded-genus graphs
• Combinatorial bounds on nonnegative rank and extended formulations

Cites work

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

Cited in

(7)

• Fooling sets and the spanning tree polytope
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• The rectangle covering number of random Boolean matrices
• On the combinatorial lower bound for the extension complexity of the spanning tree polytope
• Fooling Polytopes
• Fooling polytopes
• Smaller extended formulations for the spanning tree polytope of bounded-genus graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1705643)