-

 

 

 




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 )

Citation:

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

 

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