Paper ID: 5784
The Hospitals/Residents Problem with Ties
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
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.