An elementary integrality proof of Rothblum's stable matching formulation

DOI10.1016/J.ORL.2016.09.011zbMATH Open1408.90257arXiv1605.04427OpenAlexW2527480274MaRDI QIDQ1709952FDOQ1709952

Authors: Jochen Könemann, Kanstantsin Pashkovich, Justin Toth 

Publication date: 15 January 2019

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

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.

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

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

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)

Cites Work

• College Admissions and the Stability of Marriage
• Linear programming brings marital bliss
• Title not available (Why is that?)
• Characterization of stable matchings as extreme points of a polytope
• 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)