The Stable Marriage Polytope is Box-Totally Dual Integral
Michele Barbato, Emiliano Lancini
Source abstract
A stable matching in a bipartite preference system is a matching that has no unmatched pair whose endpoints both prefer each other to their current assignments. Rothblum gave a linear description of the stable marriage polytope, the convex hull of the incidence vectors of stable matchings. We prove that this polytope is box-totally dual integral. The proof uses the affine representation of the stable marriage polytope as an order polytope together with the matricial characterization of box-TDI polyhedra. Since Kiraly and Pap proved that Rothblum's description is totally dual integral, our result further implies that Rothblum's system is box-totally dual integral.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.