| Title | : | Popularity in the Generalized Hospital Residents Setting |
| Speaker | : | Amit Rawat (IITM) |
| Details | : | Wed, 15 Mar, 2017 3:00 PM @ BSB 361 |
| Abstract: | : | Consider the well-studied Hospital Residents (HR) problem which models several
important real-world applications like allocating projects to interns, students to electives,
and many others including assigning medical interns to hospitals in the US. The problem
can be readily modeled as a bipartite graph G = (R U H, E) where R and H denote a set
of residents and a set of hospitals respectively. Associated with each hospital is a non-zero
capacity denoting the number of residents that can be matched to the hospital. In addition,
the residents and the hospitals specify strict preferences over a subset of elements from the
other set. The goal is to assign residents to hospitals optimally while respecting the capacities
of the hospitals. Stability is a well-accepted notion of optimality in such problems, since stable allocations are guaranteed to exist. However, a stable allocation can be half the size of the largest possible allocation. We consider an alternative to stability namely popularity in the HR problem. In the first part of our work, we consider the problem of computing popular allocations in the generalized HR setting. We present efficient algorithms to compute a largest sized popular allocation, and a popular allocation amongst all the largest sized allocations. In the second part of our work, we empirically investigate the quality of popular allocations for the HR problem. Our comprehensive experimental evaluation reveals that popularity is attractive not only in terms of size, but is also appealing in terms of other parameters of practical importance. Part of this work has been accepted for publication at the 12th International Computer Science Symposium in Russia (CSR 2017). |
