Extended formulations for sparsity matroids

DOI10.1007/S10107-015-0936-8MaRDI QIDQ304267zbMATH OpenOpenAlexFDO

Authors Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh, Shuji Kijima, Yoshio Okamoto

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

zbMATH Keywords

randomized communication protocol

Mathematics Subject Classification ID

Linear programming (90C05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: We show the existence of a polynomial-size extended formulation for the base polytope of a $(k,ell)$-sparsity matroid. For an undirected graph $G=(V,E)$, the size of the formulation is $O(|V||E|)$ when $kgeqell$ and $O(|V{|}^2|E|)$ when $kleqell$. To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol.

Recommendations

• Extended formulations of lower-truncated transversal polymatroids
• Extended formulations for independence polytopes of regular matroids
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Subgraph polytopes and independence polytopes of count matroids

Cites work

• A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs
• Decomposition of regular matroids
• Edge-Disjoint Spanning Trees of Finite Graphs
• Matroids and the greedy algorithm
• NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS
• Natural realizations of sparsity matroids
• On graphs and rigidity of plane skeletal structures
• On the degrees of the vertices of a directed graph
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• Smallest compact formulation for the permutahedron
• Some \(0/1\) polytopes need exponential size extended formulations
• Subgraph polytopes and independence polytopes of count matroids
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(9)

• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• scientific article; zbMATH DE number 1303555 (Why is no real title available?)
• Extended formulations of lower-truncated transversal polymatroids
• Extended formulations for independence polytopes of regular matroids
• Subgraph polytopes and independence polytopes of count matroids
• A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
• Regular matroids have polynomial extension complexity
• Extended formulations for matroid polytopes through randomized protocols
• Smaller extended formulations for the spanning tree polytope of bounded-genus graphs

This page was built for publication: Extended formulations for sparsity matroids

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