Computing at Glasgow University
Paper ID: 5784

The Hospitals/Residents Problem with Ties
Irving,R.W. Manlove,D.F. Scott,S.

Publication Type: Conference Proceedings
Appeared in: Proceedings of SWAT 2000: The 7th Scandinavian Workshop on Algorithm Theory (Halldorsson, Magnus, M., Ed.), volume 1851 of Lecture Notes in Computer Science
Page Numbers : 259-271
Publisher: Springer
Year: 2000
ISBN/ISSN: 3-540-67690-2

URL: This publication is available at this URL.

Note: (c) Springer-Verlag


The hospitals/residents problem is an extensively-studied many-one stable matching problem. Here, we consider the hospitals/residents problem where ties are allowed in the preference lists. In this extended setting, a number of natural definitions for a stable matching arise. We present the first linear-time algorithm for the problem under the strongest of these criteria, so-called super-stability. Our new results have applications to large-scale matching schemes, such as the National Resident Matching Program in the US, and similar schemes elsewhere.

PDF Bibtex entry Endnote XML