Extended formulations for sparsity matroids

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

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


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

Original languageEnglish
Pages (from-to)565-574
Number of pages10
JournalMathematical Programming
Issue number1-2
Publication statusPublished - Jul 1 2016

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Extended formulations for sparsity matroids'. Together they form a unique fingerprint.

Cite this