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

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).

Article

Download

View PDF