Article ID: | iaor200954158 |
Country: | United States |
Volume: | 33 |
Issue: | 2 |
Start Page Number: | 283 |
End Page Number: | 290 |
Publication Date: | May 2008 |
Journal: | Mathematics of Operations Research |
Authors: | Kirly Tams, Pap Jlia |
Keywords: | duality, marriage problem, matching |
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.