Regular Matroids Have Polynomial Extension Complexity

DOI10.1287/MOOR.2021.1137zbMath1492.05024arXiv1909.08539OpenAlexW3185896300MaRDI QIDQ5076712

Manuel Aprile, Samuel Fiorini

Publication date: 17 May 2022

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

extended formulationsindependence polytoperegular matroidsspanning tree polytopecut dominant

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Integer programming (90C10) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (3)

Lifts for Voronoi cells of lattices ⋮ Advances on strictly \(\varDelta \)-modular IPs ⋮ The role of rationality in integer-programming relaxations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extended formulations for sparsity matroids
• Extended formulations for independence polytopes of regular matroids
• Decomposition of regular matroids
• Using separation algorithms to generate mixed integer model reformulations
• Expressing combinatorial optimization problems by linear programs
• On the cut polyhedron.
• Subgraph polytopes and independence polytopes of count matroids
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Correction to: ``Extended formulations for independence polytopes of regular matroids
• Some \(0/1\) polytopes need exponential size extended formulations
• A linear-size zero?one programming model for the minimum spanning tree problem in planar graphs
• Cut Dominants and Forbidden Minors
• On Vertices and Facets of Combinatorial 2-Level Polytopes
• Disjunctive Programming
• The intractability of computing the minimum distance of a code
• Extension Complexity of Independent Set Polytopes
• The Matching Polytope has Exponential Extension Complexity
• Symmetry Matters for Sizes of Extended Formulations
• Matroid Secretary for Regular and Decomposable Matroids
• Linear vs. semidefinite extended formulations
• Extended formulations in combinatorial optimization

This page was built for publication: Regular Matroids Have Polynomial Extension Complexity