Access count of this item: 137
|Title:||The Hospitals/Residents Problem with Lower Quotas|
|Author's alias:||濱田, 浩気|
|Keywords:||The stable marriage problem|
The Hospitals/Residents problem
|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. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
|Appears in Collections:||Journal Articles|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.