2015年
Finding witnesses for stability in the hospitals/residents problem
Journal of Information Processing
- ,
- ,
- 巻
- 23
- 号
- 2
- 開始ページ
- 202
- 終了ページ
- 209
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.2197/ipsjjip.23.202
- 出版者・発行元
- Information Processing Society of Japan
The Hospitals/Residents problem is a many-to-one generalization of the well-known Stable Marriage problem. Its instance consists of a set of residents, a set of hospitals, each resident’s preference list, each hospital’s preference list, and each hospital’s capacity (i.e., the number of available positions). It asks to find a stable matching between residents and hospitals. In this paper, we consider the problem of deciding, given residents’ preference lists and a matching, whether there are hospitals’ preference lists that make a given matching stable. We call this problem Stable Hospital’s Preference List problem (SHPL). It is easy to see that there always exists a solution if we allow arbitrary preference lists of hospitals. Considering more suitable situations, we pose a restricted version, called k-SHPL, in which there are only k kinds of preference lists of hospitals. We show that 1-SHPL is solvable in polynomial time, while k-SHPL is NP-complete for any k such that 2 ≤ k ≤ n1-e, where n is the number of residents and e is any positive constant. We also present four heuristics algorithms (first-fit algorithms) for 2-SHPL. We implement these algorithms and present a computational study using random instances.
- リンク情報
- ID情報
-
- DOI : 10.2197/ipsjjip.23.202
- ISSN : 1882-6652
- ISSN : 0387-5806
- DBLP ID : journals/jip/LeeMI15
- SCOPUS ID : 84924758385