Extended formulations for independence polytopes of regular matroids

DOI10.1007/S00373-016-1709-8MaRDI QIDQ343749zbMATH OpenOpenAlexFDO

Authors Volker Kaibel, Jon Lee, Matthias Walter, Stefan Weltge

Publication date 29 November 2016

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

decompositionextended formulationindependence polytoperegular matroid

Mathematics Subject Classification ID

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

Abstract: The ancillary file Corrigendum.pdf contains an explanation why our proof does not work.

Recommendations

• Regular matroids have polynomial extension complexity
• Extended formulations for sparsity matroids
• Subgraph polytopes and independence polytopes of count matroids
• Extension complexity of independent set polytopes
• Extended formulations of lower-truncated transversal polymatroids

Cites work

• A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs
• A short proof that the extension complexity of the correlation polytope grows exponentially
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• Combinatorial bounds on nonnegative rank and extended formulations
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Decomposition of regular matroids
• Extended formulations for sparsity matroids
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Linear vs. semidefinite extended formulations
• Some \(0/1\) polytopes need exponential size extended formulations
• Subgraph polytopes and independence polytopes of count matroids
• Theta rank, levelness, and matroid minors
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(10)

• Subgraph polytopes and independence polytopes of count matroids
• Ordered matroids and regular independence systems
• The facets of the matroid polytope and the independent set polytope of a positroid
• Correction to: ``Extended formulations for independence polytopes of regular matroids
• Extended formulations for matroid polytopes through randomized protocols
• Extended formulations for sparsity matroids
• A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
• Extended formulations of lower-truncated transversal polymatroids
• Regular matroids have polynomial extension complexity
• An extended formulation for the 1‐wheel inequalities of the stable set polytope

This page was built for publication: Extended formulations for independence polytopes of regular matroids

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