An elementary integrality proof of Rothblum's stable matching formulation

DOI10.1016/J.ORL.2016.09.011MaRDI QIDQ1709952zbMATH OpenOpenAlexFDO

Authors Jochen Könemann, Kanstantsin Pashkovich, Justin Toth

Publication date 15 January 2019

Published in Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

polytopeextreme pointsstable matching

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)

Abstract: In this paper we provide a short new proof for the integrality of Rothblum's linear description of the convex hull of incidence vectors of stable matchings in bipartite graphs. In the spirit of iterative rounding proofs, the key feature of our proof is to show that extreme points of the formulation must have a 0, 1-component.

Recommendations

• Total Dual Integrality of Rothblum's Description of the Stable-Marriage Polyhedron
• Characterization of stable matchings as extreme points of a polytope
• The geometry of fractional stable matchings and its applications
• On the stable b-matching polytope.
• Stable matchings and linear programming

Cites work

• scientific article; zbMATH DE number 477584 (Why is no real title available?)
• Characterization of stable matchings as extreme points of a polytope
• College Admissions and the Stability of Marriage
• Linear programming brings marital bliss
• On the stable marriage polytope

Cited in

(1)

• Popularity, Mixed Matchings, and Self-Duality

This page was built for publication: An elementary integrality proof of Rothblum's stable matching formulation

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