| 講演名 | 1998/11/20 条件を緩和した安定結婚問題のNP完全性について 宮崎 修一, 岩間 一雄, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 安定結婚問題は, 入力としてN人ずつの男女と各個人の異性に対する希望リスト(異性N人の順序付け)が与えられ, 安定なN組のペアを求める(安定なN組のペアが存在するかどうかを問う)問題である.本問題の自然な拡張として, (i)希望リストに異性N人全員を書かなくても良いもの, (ii)希望の順序付けに半順序を許すもの, があるが, いずれも解の存在は多項式時間で判定できることが知られている.本研究では, (i)および(ii)を同時に許した場合に, 本問題がNP完全になることを示す.また, 本問題に関連した問題のNP完全性も示す. |
| 抄録(英) | The original stable marriage problem requires both each man and woman to submit a complete and strict order of his/her preference, i.e., a total order list of, say, 100 people, if there are 100 men and women. This is obviously unrealistic often in practice, and several relaxations have been proposed, including the following two common ones: One is to allow an incomplete list, i.e., a man is allowed to accept only a subset of the women and vice versa. The other is to allow a "weaker"preference list such as a list including ties and partial orders. A little surprisingly, it is known that both problems can still be solved in polynomial time. In this paper, we show that the problem becomes NP-hard, if we allow both relaxations(incomplete lists and partial orders)at the same time. |
| キーワード(和) | 安定結婚問題 / 半順序 / 学生配偶問題 / NP完全性 |
| キーワード(英) | stable marriage / problem / partial order / student assignment problem / NP-completeness |
| 資料番号 | COMP98-55 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1998/11/20(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 条件を緩和した安定結婚問題のNP完全性について |
| サブタイトル（和） | |
| タイトル（英） | On the NP-Completeness of Weakly Stable Marriage |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 安定結婚問題 / stable marriage |
| キーワード(2)（和/英） | 半順序 / problem |
| キーワード(3)（和/英） | 学生配偶問題 / partial order |
| キーワード(4)（和/英） | NP完全性 / student assignment problem |
| 第 1 著者 氏名（和/英） | 宮崎 修一 / Shuichi Miyazaki |
| 第 1 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 2 著者 氏名（和/英） | 岩間 一雄 / Kazuo Iwama |
| 第 2 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 発表年月日 | 1998/11/20 |
| 資料番号 | COMP98-55 |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 432 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |