| Item type |
JInfP(1) |
| 公開日 |
2015-03-15 |
| タイトル |
|
|
タイトル |
Finding Witnesses for Stability in the Hospitals/Residents Problem |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Finding Witnesses for Stability in the Hospitals/Residents Problem |
| 言語 |
|
|
言語 |
eng |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[Regular Papers (Recommended Paper)] the Hospitals/Residents problem, hospital's preference list, NP-complete, first-fit algorithm |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者所属 |
|
|
|
Graduate School of Informatics, Kyoto University |
| 著者所属 |
|
|
|
Academic Center for Computing and Media Studies, Kyoto University |
| 著者所属 |
|
|
|
Graduate School of Informatics, Kyoto University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Informatics, Kyoto University |
| 著者所属(英) |
|
|
|
en |
|
|
Academic Center for Computing and Media Studies, Kyoto University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Informatics, Kyoto University |
| 著者名 |
Minseon, Lee
Shuichi, Miyazaki
Kazuo, Iwama
|
| 著者名(英) |
Minseon, Lee
Shuichi, Miyazaki
Kazuo, Iwama
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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-ε, where n is the number of residents and ε 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. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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-ε, where n is the number of residents and ε 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 |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA00700121 |
| 書誌情報 |
Journal of information processing
巻 23,
号 2,
p. 202-209,
発行日 2015-03-15
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-6652 |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-JIP2302016.pdf (460.2 kB)
