<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>5784</REFNUM><AUTHORS><AUTHOR>Irving,R.W.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>Scott,S.</AUTHOR></AUTHORS><YEAR>2000</YEAR><TITLE>The Hospitals/Residents Problem with Ties</TITLE><PLACE_PUBLISHED>Proceedings of SWAT 2000: The 7th Scandinavian Workshop on Algorithm Theory (Halldorsson, Magnus, M., Ed.), volume 1851 of Lecture Notes in Computer Science</PLACE_PUBLISHED><PUBLISHER>Springer</PUBLISHER><PAGES>259-271</PAGES><ISBN>3-540-67690-2</ISBN><LABEL>Irving:2000:5784</LABEL><ABSTRACT>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 <i>super-stability</i>. Our new results have applications to large-scale matching schemes, such as the National Resident Matching Program in the US, and similar schemes elsewhere.</ABSTRACT><NOTES>(c) Springer-Verlag <p></NOTES><URL>http://www.springerlink.com/content/82paa7xcvmh4l458/?p=3ec51444e2374cb8b6e25718491c8ebc&pi=23</URL></RECORD></RECORDS></XML>