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

DOI10.1137/16M1089691MaRDI QIDQ5232142zbMATH OpenOpenAlexFDO

Authors Matthias Walter

Publication date 29 August 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.01880

zbMATH Keywords

bipartite matchingmatching polytopequadratic matching problem

Mathematics Subject Classification ID

Quadratic programming (90C20) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: We consider, for complete bipartite graphs, the convex hulls of characteristic vectors of all matchings, extended by a binary entry indicating whether the matching contains two specific edges. These polytopes are associated to the quadratic matching problems 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). In addition, we also derive facetness and separation results for the polytopes. The completeness proof is based on a geometric relationship to a matching polytope of a nonbipartite graph. Using standard techniques, we finally extend the result to capacitated b-matchings.

Recommendations

• Matching graphs of hypercubes and complete bipartite graphs
• Matching graphs of Hypercubes and Complete Bipartite Graphs
• Matching structure of symmetric bipartite graphs and a generalization of Pólya's problem
• A linear algorithm for a perfect matching in polyomino graphs
• A quadratic form characterization of completeN-partite graphs
• A complete description of convex sets associated with matchings and edge‐connectivity in graphs
• The graph of perfect matching polytope and an extreme problem
• scientific article; zbMATH DE number 2188337
• scientific article; zbMATH DE number 1431747
• A linear time algorithm for maximum matchings in convex, bipartite graphs

Cites work

• A Short Proof of the Factor Theorem for Finite Graphs
• A survey for the quadratic assignment problem
• An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations
• Combinatorial optimization with one quadratic term: spanning trees and forests
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complete description for the spanning tree problem with one linearised quadratic term
• Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 1187168 (Why is no real title available?)
• scientific article; zbMATH DE number 1173721 (Why is no real title available?)
• scientific article; zbMATH DE number 3095897 (Why is no real title available?)
• Matroid optimisation problems with nested non-linear monomials in the objective function
• Maximum matching and a polyhedron with 0,1-vertices
• Odd Minimum Cut-Sets and b-Matchings
• On minimum reload cost cycle cover
• P-Complete Approximation Problems
• Paths, Trees, and Flowers
• Short proofs on the matching polyhedron
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(5)

• Facets of an assignment problem with 0-1 constraint
• Matroid optimization problems with monotone monomials in the objective
• The disjunctive procedure on the matching problem
• The bilinear–biquadratic model on the complete graph
• Normality of k-matching polytopes of bipartite graphs

This page was built for publication: Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232142)