Optimization Online


Extended Formulations for Independence Polytopes of Regular Matroids

Volker Kaibel(kaibel***at***ovgu.de)
Jon Lee(jonxlee***at***umich.edu)
Matthias Walter(matthias.walter***at***ovgu.de)
Stefan Weltge(weltge***at***ovgu.de)

Abstract: We show that the independence polytope of every regular matroid has an extended formulation of size quadratic in the size of its ground set. This generalizes a similar statement for (co-)graphic matroids, which is a simple consequence of Martin's extended formulation for the spanning-tree polytope. In our construction, we make use of Seymour's decomposition theorem for regular matroids. As a consequence, the extended formulations can be computed in polynomial time.

Keywords: extended formulation, independence polytope, regular matroid, decomposition

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [PDF]

Entry Submitted: 04/16/2015
Entry Accepted: 04/17/2015
Entry Last Modified: 04/16/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society