Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
From MaRDI portal
Publication:2121739
DOI10.37236/10522zbMath1489.05132arXiv2106.11945OpenAlexW3177095386MaRDI QIDQ2121739
Samuel Fiorini, Manuel Aprile, Tony Huynh, Gwenaël Joret, David R. Wood
Publication date: 4 April 2022
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2106.11945
Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Graph minors (05C83) Connectivity (05C40)
Related Items (5)
Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes ⋮ Extended formulations for matroid polytopes through randomized protocols ⋮ The role of rationality in integer-programming relaxations ⋮ Linear-size formulations for connected planar graph partitioning and political districting ⋮ A polyhedral perspective on tropical convolutions
Cites Work
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- Smaller extended formulations for the spanning tree polytope of bounded-genus graphs
- Extended formulations, nonnegative factorizations, and randomized communication protocols
- Lower bound of the Hadwiger number of graphs by their average degree
- Matroid polytopes, nested sets and Bergman fans
- Using separation algorithms to generate mixed integer model reformulations
- Expressing combinatorial optimization problems by linear programs
- Subgraph polytopes and independence polytopes of count matroids
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Layered separators in minor-closed graph classes with applications
- On the combinatorial lower bound for the extension complexity of the spanning tree polytope
- Some \(0/1\) polytopes need exponential size extended formulations
- Extended formulations for matroid polytopes through randomized protocols
- A linear-size zero?one programming model for the minimum spanning tree problem in planar graphs
- Strongly Sublinear Separators and Polynomial Expansion
- Quantum strategic game theory
- On Vertices and Facets of Combinatorial 2-Level Polytopes
- A separator theorem for graphs of bounded genus
- An extremal function for contractions of graphs
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- A Separator Theorem for Nonplanar Graphs
- Separators for sphere-packings and nearest neighbor graphs
- A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
- Separators in region intersection graphs
- Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
- Sublinear Separators in Intersection Graphs of Convex Shapes
- Structure of Graphs with Locally Restricted Crossings
- Extension Complexity, MSO Logic, and Treewidth
- Matroids and the greedy algorithm
- Extended formulations from communication protocols in output-efficient time
This page was built for publication: Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
