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

Research output: Contribution to journalArticleAcademicpeer-review

9 Downloads (Pure)

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. This polytope is associated with the quadratic matching problem with a single linearized quadratic term. We provide a complete irredundant inequality description, which settles a conjecture by Klein [Combinatorial Optimization with One Quadratic Term, Ph.D. thesis, TU Dortmund, Dortmund, Germany]. 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.

Original languageEnglish
Pages (from-to)1061-1094
Number of pages34
JournalSIAM journal on discrete mathematics
Volume33
Issue number2
DOIs
Publication statusPublished - 27 Jun 2019

Keywords

  • quadratic matching problem
  • matching polytope
  • bipartite matching

Cite this

@article{1c502d6e0ce44356bb462aaf20ca325e,
title = "Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs",
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. This polytope is associated with the quadratic matching problem with a single linearized quadratic term. We provide a complete irredundant inequality description, which settles a conjecture by Klein [Combinatorial Optimization with One Quadratic Term, Ph.D. thesis, TU Dortmund, Dortmund, Germany]. 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.",
keywords = "quadratic matching problem, matching polytope, bipartite matching",
author = "Matthias Walter",
year = "2019",
month = "6",
day = "27",
doi = "10.1137/16M1089691",
language = "English",
volume = "33",
pages = "1061--1094",
journal = "SIAM journal on discrete mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",

}

Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs. / Walter, Matthias.

In: SIAM journal on discrete mathematics, Vol. 33, No. 2, 27.06.2019, p. 1061-1094.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Walter, Matthias

PY - 2019/6/27

Y1 - 2019/6/27

N2 - 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. This polytope is associated with the quadratic matching problem with a single linearized quadratic term. We provide a complete irredundant inequality description, which settles a conjecture by Klein [Combinatorial Optimization with One Quadratic Term, Ph.D. thesis, TU Dortmund, Dortmund, Germany]. 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.

AB - 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. This polytope is associated with the quadratic matching problem with a single linearized quadratic term. We provide a complete irredundant inequality description, which settles a conjecture by Klein [Combinatorial Optimization with One Quadratic Term, Ph.D. thesis, TU Dortmund, Dortmund, Germany]. 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.

KW - quadratic matching problem

KW - matching polytope

KW - bipartite matching

U2 - 10.1137/16M1089691

DO - 10.1137/16M1089691

M3 - Article

VL - 33

SP - 1061

EP - 1094

JO - SIAM journal on discrete mathematics

JF - SIAM journal on discrete mathematics

SN - 0895-4801

IS - 2

ER -