This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Király, T. Articles by Pap, J. Search for Related Content

Total Dual Integrality of Rothblum's Description of the Stable-Marriage Polyhedron

MTA-ELTE Egerváry Research Group, Eötvös Loránd University, Pázmány Péter sétány 1/C, H-1117 Budapest, Hungary
Eötvös Loránd University, Pázmány sétány 1/C, H-1117 Budapest, Hungary
tkiraly{at}cs.elte.hu, http://www.cs.elte.hu/tkiraly
papjuli{at}cs.elte.hu

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.

Key Words: stable marriage; total dual integrality; rotations
History: Received: April 27, 2005; revision received: March 1, 2007;