2016/07/07 by Matthias Walter, Walter, Matthias
Computer Science · Engineering · Mathematics · #52B99 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Point processes and geometric inequalities #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1607.01880
openalex publication_date 2016/07/07 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
We consider, for complete bipartite graphs, the convex hulls of\ncharacteristic vectors of all matchings, extended by a binary entry indicating\nwhether the matching contains two specific edges. These polytopes are\nassociated to the quadratic matching problems with a single linearized\nquadratic term. We provide a complete irredundant inequality description, which\nsettles a conjecture by Klein (Ph.D. thesis, TU Dortmund, 2015). In addition,\nwe also derive facetness and separation results for the polytopes. The\ncompleteness proof is based on a geometric relationship to a matching polytope\nof a nonbipartite graph. Using standard techniques, we finally extend the\nresult to capacitated b-matchings.\n