The Hospitals/Residents Problem with Lower Quotas

• Published in: Algorithmica 2016-01, Vol.74 (1), p.440-465
• Main Authors: Hamada, Koki, Iwama, Kazuo, Miyazaki, Shuichi
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Mathematics of Computing; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-014-9951-z

The Hospitals/Residents problem is a many-to-one extension of the stable marriage problem. In an instance, each hospital specifies a quota, i.e., an upper bound on the number of positions it provides. It is well-known that in any instance, there exists at least one stable matching, and finding one can be done in polynomial time. In this paper, we consider an extension in which each hospital specifies not only an upper bound but also a lower bound on its number of positions. In this setting, there can be instances that admit no stable matching, but the problem of asking if there is a stable matching is solvable in polynomial time. In case there is no stable matching, we consider the problem of finding a matching that is “as stable as possible”, namely, a matching with a minimum number of blocking pairs. We show that this problem is hard to approximate within the ratio of ( | H | + | R | ) 1 - ϵ for any positive constant ϵ where H and R are the sets of hospitals and residents, respectively. We then tackle this hardness from two different angles. First, we give an exponential-time exact algorithm whose running time is O ( ( | H | | R | ) t + 1 ) , where t is the number of blocking pairs in an optimal solution. Second, we consider another measure for optimization criteria, i.e., the number of residents who are involved in blocking pairs. We show that this problem is still NP-hard but has a polynomial-time | R | -approximation algorithm.