Academic
Publications
Stable marriage with ties and bounded length preference lists

Stable marriage with ties and bounded length preference lists,10.1016/j.jda.2008.09.003,Journal of Discrete Algorithms,Robert W. Irving,David F. Manlo

Stable marriage with ties and bounded length preference lists   (Citations: 4)
BibTex | RIS | RefWorks Download
We consider variants of the classical stable marriage problem in which preference lists may contain ties, and may be of bounded length. Such restrictions arise naturally in practical applications, such as centralised matching schemes that assign graduating medical students to their first hospital posts. In such a setting, weak stability is the most common solution concept, and it is known that weakly stable matchings can have different sizes. This motivates the problem of finding a maximum cardinality weakly stable matching, which is known to be NP-hard in general. We show that this problem is solvable in polynomial time if each man's list is of length at most 2 (even for women's lists that are of unbounded length). However if each man's list is of length at most 3, we show that the problem becomes NP-hard (even if each women's list is of length at most 3) and not approximable within some δ>1 (even if each woman's list is of length at most 4).
Journal: Journal of Discrete Algorithms - JDA , vol. 7, no. 2, pp. 213-219, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...If the length of each man’s list is bounded by 2, it is solvable in polynomial time even if women’s lists are of arbitrary length, while it is NP-hard even if the length of each preference list is bounded by 3 [8]...

    Kazuo Iwamaet al. A 25/17Approximation Algorithm for the Stable Marriage Problem with On...

    • ...problem of nding a stable matching of maximum cardinality (henceforth a maximum stable matching) for an instance of HRT { problem MAX-HRT { is NP-hard [20, 15], even under severe restrictions...
    • ...Also, MAX-HRT is NP-hard even if each hospital has capacity 1, each preference list is of length at most 3, and each resident’s list is strictly ordered [15]...

    Robert W. Irvinget al. Finding large stable matchings

Sort by: