UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 8773

The Stable Marriage Problem with Master Preference Lists
Irving,R.W. Manlove,D.F. Scott,S.

Publication Type: Journal
Appeared in: Discrete Applied Mathematics, volume 156
Page Numbers : 2959-2977
Publisher: Elsevier Science
Year: 2008
ISBN/ISSN:

URL: This publication is available at this URL.

Abstract:

We study variants of the classical stable marriage problem in which the preferences of the men or the women, or both, are derived from a master preference list. This models real-world matching problems in which participants are ranked according to some objective criteria. The master list(s) may be strictly ordered, or may include ties, and the lists of individuals may involve ties and may include all, or just some, of the members of the opposite sex. In fact, ties are almost inevitable in the master list if the ranking is done on the basis of a scoring scheme with a relatively small range of distinct values. We show that many of the interesting variants of stable marriage that are NP-hard remain so under very severe restrictions involving the presence of master lists, but a number of special cases can be solved in polynomial time. Under this master list model, versions of the stable marriage problem that are already solvable in polynomial time typically yield to faster and/or simpler algorithms, giving rise to simple new structural characterisations of the solutions in these cases.

Keywords: Matching; Preferences; Stability; Ties; Polynomial-time algorithm; NP-hardness


PDF Bibtex entry Endnote XML