ダウンロード数: 326
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
LIPIcs-ISAAC-2017-56.pdf | 488.66 kB | Adobe PDF | 見る/開く |
タイトル: | Jointly stable matchings |
著者: | Miyazaki, Shuichi Okamoto, Kazuya https://orcid.org/0000-0002-9079-2253 (unconfirmed) |
著者名の別形: | 宮崎, 修一 岡本, 和也 |
キーワード: | stable marriage problem stable matching NP-completeness linear time algorithm |
発行日: | 2017 |
出版者: | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
誌名: | Leibniz International Proceedings in Informatics, LIPIcs |
巻: | 92 |
開始ページ: | 56:1 |
終了ページ: | 56:12 |
抄録: | 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 L_i (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 L_i. We show that the decision problem is NP-complete already for k=2, even if each person's preference list is of length at most four, while 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 L_i, then the problem can be solved in linear time. |
記述: | 28th International Symposium on Algorithms and Computation (ISAAC 2017) |
著作権等: | © Shuichi Miyazaki and Kazuya Okamoto; licensed under Creative Commons License CC-BY |
URI: | http://hdl.handle.net/2433/234947 |
DOI(出版社版): | 10.4230/LIPIcs.ISAAC.2017.56 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。