Extended formulations for sparsity matroids
From MaRDI portal
Publication:304267
DOI10.1007/s10107-015-0936-8zbMath1343.05046arXiv1403.7272OpenAlexW1538034711MaRDI QIDQ304267
Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh, Yoshio Okamoto, Shuji Kijima
Publication date: 25 August 2016
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1403.7272
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)
Related Items (6)
Extended formulations for independence polytopes of regular matroids ⋮ Regular Matroids Have Polynomial Extension Complexity ⋮ Extended formulations for matroid polytopes through randomized protocols ⋮ 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 ⋮ Extended formulations of lower-truncated transversal polymatroids
Cites Work
- Smallest compact formulation for the permutahedron
- Extended formulations, nonnegative factorizations, and randomized communication protocols
- Rigidity of multi-graphs. I: Linking rigid bodies in n-space
- Decomposition of regular matroids
- Using separation algorithms to generate mixed integer model reformulations
- Subgraph polytopes and independence polytopes of count matroids
- Some \(0/1\) polytopes need exponential size extended formulations
- On the degrees of the vertices of a directed graph
- On graphs and rigidity of plane skeletal structures
- A linear-size zero?one programming model for the minimum spanning tree problem in planar graphs
- NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS
- Natural realizations of sparsity matroids
- Edge-Disjoint Spanning Trees of Finite Graphs
- Matroids and the greedy algorithm
This page was built for publication: Extended formulations for sparsity matroids
