Extended formulations for independence polytopes of regular matroids

DOI10.1007/s00373-016-1709-8zbMath1354.05021arXiv1504.03872OpenAlexW3101338581MaRDI QIDQ343749

Mohammad Hasan, M. Dambrine

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

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

Related Items (4)

Regular Matroids Have Polynomial Extension Complexity ⋮ An extended formulation for the 1‐wheel inequalities of the stable set polytope ⋮ A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs” ⋮ On Vertices and Facets of Combinatorial 2-Level Polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extended formulations for sparsity matroids
• Theta rank, levelness, and matroid minors
• Decomposition of regular matroids
• Using separation algorithms to generate mixed integer model reformulations
• Combinatorial bounds on nonnegative rank and extended formulations
• Subgraph polytopes and independence polytopes of count matroids
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A short proof that the extension complexity of the correlation polytope grows exponentially
• 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
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• The Matching Polytope has Exponential Extension Complexity
• Linear vs. semidefinite extended formulations

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