Downloads: 393

Files in This Item:
File Description SizeFormat 
s00453-014-9951-z.pdf286.45 kBAdobe PDFView/Open
Title: The Hospitals/Residents Problem with Lower Quotas
Authors: Hamada, Koki
Iwama, Kazuo
Miyazaki, Shuichi  KAKEN_id  orcid https://orcid.org/0000-0003-0369-1970 (unconfirmed)
Author's alias: 濱田, 浩気
岩間, 一雄
宮崎, 修一
Keywords: The stable marriage problem
The Hospitals/Residents problem
Stable matching
Approximation algorithm
Issue Date: Jan-2016
Publisher: Springer US
Journal title: Algorithmica
Volume: 74
Issue: 1
Start page: 440
End page: 465
Abstract: 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 (Formula Presented) 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 (Formula Presented), 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 (Formula Presented)-approximation algorithm.
Rights: The final publication is available at Springer via https://doi.org/10.1007/s00453-014-9951-z
The full-text file will be made open to the public 01 January 2017 in accordance with publisher's 'Terms and Conditions for Self-Archiving'.
この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
This is not the published version. Please cite only the published version.
URI: http://hdl.handle.net/2433/226943
DOI(Published Version): 10.1007/s00453-014-9951-z
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.