このアイテムのアクセス数: 3

このアイテムのファイル:
ファイル 記述 サイズフォーマット 
IEICE_tec.rep_COMP98-55.pdf2.02 MBAdobe PDF見る/開く
タイトル: On the NP-Completeness of weakly stable marriage
その他のタイトル: 条件を緩和した安定結婚問題のNP完全性について
著者: Miyazaki, Shuichi
Iwama, Kazuo
著者名の別形: 宮崎, 修一
岩間, 一雄
キーワード: stable marriage problem
partial order
student assignment problem
NP-completeness
安定結婚問題
半順序
学生配属問題
NP完全性
発行日: 20-Nov-1998
出版者: Institute of Electronics, Information and Communications Engineers (IEICE)
誌名: 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報
巻: 98
号: 432
開始ページ: 33
終了ページ: 40
論文番号: COMP98-55
抄録: 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.
安定結婚問題は,入力としてN人ずつの男女と各個人の異性に対する希望リスト(異性N人の順序付け)が与えられ,安定なN組のペアを求める(安定なN組のペアが存在するかどうかを問う)問題である.本問題の自然な拡張として,(i)希望リストに異性N人全員を書かなくても良いもの,(ii)希望の順序付けに半順序を許すもの,があるが,いずれも解の存在は多項式時間で判定できることが知られている.本研究では,(i)および(ii)を同時に許した場合に,本問題がNP完全になることを示す.また,本問題に関連した問題のNP完全性も示す.
著作権等: © 1998 by the Institute of Electronics, Information and Communications Engineers (IEICE)
URI: http://hdl.handle.net/2433/227134
関連リンク: http://db.ieice.org/gakkai/show.php?id=105066
出現コレクション:学術雑誌掲載論文等

アイテムの詳細レコードを表示する

Export to RefWorks


出力フォーマット 


このリポジトリに保管されているアイテムはすべて著作権により保護されています。