ダウンロード数: 100
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
s10878-019-00402-4.pdf | 123.16 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Miyazaki, Shuichi | en |
dc.contributor.author | Okamoto, Kazuya | en |
dc.contributor.alternative | 宮崎, 修一 | ja |
dc.contributor.alternative | 岡本, 和也 | ja |
dc.date.accessioned | 2019-09-03T03:34:43Z | - |
dc.date.available | 2019-09-03T03:34:43Z | - |
dc.date.issued | 2019-8 | - |
dc.identifier.issn | 1382-6905 | - |
dc.identifier.issn | 1573-2886 | - |
dc.identifier.uri | http://hdl.handle.net/2433/243846 | - |
dc.description.abstract | In the stable marriage problem, we are given a set of men, a set of women, and each person’s preference list. Our task is to find a stable matching, that is, a matching admitting no unmatched (man, woman)-pair each of which improves the situation by being matched together. It is known that any instance admits at least one stable matching. In this paper, we consider a natural extension where k( ≥ 2) sets of preference lists Li (1≤ i ≤ k ) over the same set of people are given, and the aim is to find a jointly stable matching, a matching that is stable with respect to all Li . We show that the decision problem is NP-complete for the following two restricted cases; (1) k = 2 and each person’s preference list is of length at most four, and (2) k = 4 , each man’s preference list is of length at most three, and each woman’s preference list is of length at most four. On the other hand, we show that it is solvable in linear time for any k if each man’s preference list is of length at most two (women’s lists can be of unbounded length). We also show that if each woman’s preference lists are same in all Li , then the problem can be solved in linear time. | en |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Springer US | en |
dc.rights | This is a post-peer-review, pre-copyedit version of an article published in 'Journal of Combinatorial Optimization'. The final authenticated version is available online at: https://doi.org/10.1007/s10878-019-00402-4. | en |
dc.rights | The full-text file will be made open to the public on 19 March 2020 in accordance with publisher's 'Terms and Conditions for Self-Archiving'. | en |
dc.rights | この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 | ja |
dc.rights | This is not the published version. Please cite only the published version. | en |
dc.subject | Stable marriage problem | en |
dc.subject | Stable matching | en |
dc.subject | NP-completeness | en |
dc.subject | Linear time algorithm | en |
dc.title | Jointly stable matchings | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.jtitle | Journal of Combinatorial Optimization | - |
dc.identifier.volume | 38 | - |
dc.identifier.issue | 2 | - |
dc.identifier.spage | 646 | - |
dc.identifier.epage | 665 | - |
dc.relation.doi | 10.1007/s10878-019-00402-4 | - |
dc.textversion | author | - |
dc.address | Academic Center for Computing and Media Studies Kyoto University | en |
dc.address | Division of Medical Information Technology and Administration Planning Kyoto University Hospital | en |
dcterms.accessRights | open access | - |
datacite.date.available | 2020-03-19 | - |
datacite.awardNumber | 15K00466 | - |
datacite.awardNumber | 16K00017 | - |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName.alternative | Japan Society for the Promotion of Science (JSPS) | en |
jpcoar.funderName.alternative | Japan Society for the Promotion of Science (JSPS) | en |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。