09:30-10:30 (room: SJ1Z17T/VKM)
David Manlove: Hard Variants of the Hospitals/Residents Problem
In the classical Hospitals / Residents problem (HR), we have a set of residents and a set of hospitals, where each resident ranks in strict order of preference a subset of the hospitals (and vice versa). Each hospital has a capacity, indicating the maximum number of residents that can be assigned to it. A solution is a stable matching M comprising mutually acceptable resident-hospital pairs, in which each resident has at most one hospital, no hospital exceeds its capacity, and there is no resident-hospital pair who would prefer to be assigned to one another than to remain with their existing assignments in M (if any). In 1962 Gale and Shapley described a linear-time algorithm to find a stable matching in an instance of HR.
In this talk we focus on variants of HR that are motivated by practical applications, each of which leads to NP-hard problems, in contrast to the complexity of the classical case. Variants that we consider involve (i) trading off size with stability, where we seek larger matchings that minimise instability, (ii) allowing ties in the preference lists, (iii) allowing couples to apply jointly to pairs of hospitals that are typically geographically close, (iv) allowing hospitals to have lower quotas as well as upper quotas, (v) considering a restricted form of stability called “social stability”, where only acquainted pairs can block a matching, and (vi) allowing some pairs to be forced and/or forbidden in a given matching. In each case we motivate and define the problem, survey existing algorithmic results and outline some open cases.
This is joint work with Georgios Askalidis, Péter Biró, Ágnes Cseh, Tamás Fleiner, Nicole Immorlica, Rob Irving, Augustine Kwanashie, Iain McBride, Eric McDermid, Shubham Mittal, Emmanouil Pountourakis and James Trimble.
