An Elementary Integrality Proof of Rothblum's Stable Matching Formulation
classification
🧮 math.CO
cs.DM
keywords
proofformulationintegralityrothblumstablebipartitecomponentconvex
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.