Extended Formulations for Polytopes of Regular Matroids

Rohit Gurjar, Nisheeth K. Vishnoi

Abstract

We present a simple proof of the fact that the base (and independence) polytope of a rank $n$ regular matroid over $m$ elements has an extension complexity $O(mn)$.
BibTeX
@misc{gurjar2016extended,
  author = {Rohit Gurjar and Nisheeth K. Vishnoi},
  title = {{Extended Formulations for Polytopes of Regular Matroids}},
  year = {2016},
  eprint = {1701.00538},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1701.00538},
}

Loading related content...

Figure