Optimization Online


Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs

Matthias Walter(walter***at***or.rwth-aachen.de)

Abstract: We consider, for complete bipartite graphs, the convex hulls of characteristic vectors of matchings, extended by a binary number indicating whether the matching contains two specific edges. This polytope is associated to the quadratic matching problem with a single linearized quadratic term. We provide a complete irredundant inequality description, which settles a conjecture by Klein (Ph.D. thesis, TU Dortmund, 2015).

Keywords: bipartite one term quadratic matching polytope

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 07/07/2016
Entry Accepted: 07/07/2016
Entry Last Modified: 07/07/2016

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