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

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

0.00 Avg rating0 Votes
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: ,
Keywords: duality, marriage problem, matching
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 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.

Reviews

Required fields are marked *. Your email address will not be published.