TR-2005-01

Rothblum's description of the stable marriage polyhedron is TDI

Tamás Király, Júlia Pap

Published in:
Mathematics of Operations Research 33:2 (2008), 283-290.



Abstract

Rothblum showed that the convex hull of the stable matchings of a bipartite preference system can be described by an elegant system of linear inequalities. In this note we show that the description given by Rothblum is totaly dual integral. Our proof is based on the results of Gusfield and Irving on rotations.


Bibtex entry:

@techreport{egres-05-01,
AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia},
TITLE = {Rothblum's description of the stable marriage polyhedron is TDI},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2005},
NUMBER = {TR-2005-01}
}


Last modification: 15.9.2018. Please email your comments to Tamás Király!