Optimization Online


On Matroid Parity and Matching Polytopes

Konstantinos Kaparis(K.Kaparis***at***uom.edu.gr)
Adam Letchford(A.N.Letchford***at***lancaster.ac.uk)
Ioannis Mourtos(mourtos***at***aueb.gr)

Abstract: The "matroid parity" (MP) problem is a natural extension of the matching problem to the matroid setting. It can be formulated as a 0-1 linear program using the so-called "rank" and "line" constraints. We call the associated family of polytopes "MP polytopes". We then prove the following: (i) when the matroid is a gammoid, each MP polytope is a projection of a perfect matching polytope into a suitable subspace; (ii) when the matroid is laminar, each MP polytope is affinely congruent to a perfect matching polytope; (iii) even if the matroid is laminar, MP polytopes can have facets that are defined by inequalities with non-ternary left-hand side coefficients; (iv) for any matroid, the elementary closure of the continuous relaxation of the rank-and-line formulation is equal to its {0,1/2}-closure.

Keywords: matroids; gammoids; polyhedral combinatorics

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Combinatorial Optimization (Polyhedra )

Citation: Technical report, Department of Management Science, Lancaster University, March 2017.

Download: [PDF]

Entry Submitted: 03/17/2017
Entry Accepted: 03/17/2017
Entry Last Modified: 03/17/2017

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