Total dual integrality of Rothblum´s description of the stable marriage polyhedron
Megjelenés dátuma: 2008
WoS ID: 000256197100002
Scopus ID: 61349112155
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 paper we prove that the description given by Rothblum is totally dual integral. We give a constructive proof based on the results of Gusfield and Irving on rotations, which gives rise to a strongly polynomial algorithm for finding an integer optimal dual solution.