Computing at Glasgow University
Paper ID: 6233

The Stable Roommates Problem with Ties
Irving,R.W. Manlove,D.F.

Publication Type: Journal
Appeared in: Journal of Algorithms, volume 43
Page Numbers : 85-105
Publisher: Academic Press
Year: 2002
ISBN/ISSN: 0196-6774

URL: This publication is available at this URL.


We study the variant of the well-known stable roommates problem in which participants are permitted to express ties in their preference lists. In this setting, more than one definition of stability is possible. Here we consider two of these stability criteria, so-called super-stability and weak stability. We present a linear–time algorithm for finding a super-stable matching if one exists, given a stable roommates instance with ties. This contrasts with the known NP-hardness of the analogous problem under weak stability. We also extend our algorithm to cope with preference lists that are incomplete and/or partially ordered. On the other hand, for a given stable roommates instance with ties and incomplete lists, we show that the weakly stable matchings may be of different sizes and the problem of finding a maximum cardinality weakly stable matching is NP-hard, though approximable within a factor of 2.

Keywords: stable matching; indifference; super-stability; weak stability; linear–time algorithm; NP-completeness; approximation algorithm

PDF Bibtex entry Endnote XML