The Hospitals/Residents Problem with Ties

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 superstability. Our new results have applications to large-scale matching schemes, such as the National Resident Matching Program in the US, and similar schemes elsewhere.