ダウンロード数: 250
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
ipsjjip.23.202.pdf | 449.6 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Lee, Minseon | en |
dc.contributor.author | Miyazaki, Shuichi | en |
dc.contributor.author | Iwama, Kazuo | en |
dc.contributor.alternative | 李, ミンソン | ja |
dc.contributor.alternative | 宮崎, 修一 | ja |
dc.contributor.alternative | 岩間, 一雄 | ja |
dc.date.accessioned | 2015-06-26T05:15:41Z | - |
dc.date.available | 2015-06-26T05:15:41Z | - |
dc.date.issued | 2015-03-15 | - |
dc.identifier.issn | 1882-6652 | - |
dc.identifier.uri | http://hdl.handle.net/2433/198566 | - |
dc.description.abstract | 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. | en |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Information Processing Society of Japan | en |
dc.rights | © 2015 by the Information Processing Society of Japan | en |
dc.subject | the Hospitals/Residents problem | en |
dc.subject | hospital's preference list | en |
dc.subject | NP-complete | en |
dc.subject | first-fit algorithm | en |
dc.title | Finding Witnesses for Stability in the Hospitals/Residents Problem | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.jtitle | Journal of Information Processing | en |
dc.identifier.volume | 23 | - |
dc.identifier.issue | 2 | - |
dc.identifier.spage | 202 | - |
dc.identifier.epage | 209 | - |
dc.relation.doi | 10.2197/ipsjjip.23.202 | - |
dc.textversion | publisher | - |
dcterms.accessRights | open access | - |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。