ダウンロード数: 173
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
IEICE_tec.rep_COMP2009-37.pdf | 2.22 MB | Adobe PDF | 見る/開く |
タイトル: | 最大サイズ最大安定度マッチング問題に対する近似下限の改良 |
その他のタイトル: | An Improved Approximation Lower Bound for Maximum Cardinality Almost Stable Matching Problem |
著者: | 濱田, 浩気 宮崎, 修一 岩間, 一雄 |
著者名の別形: | Hamada, Koki Miyazaki, Shuichi Iwama, Kazuo |
キーワード: | 安定結婚問題 近似アルゴリズム 近似度 多項式時間変換 the stable marriage problem approximation algorithms approximation ratio polynomial-time reduction |
発行日: | 9-Oct-2009 |
出版者: | 電子情報通信学会 |
誌名: | 電子情報通信学会技術研究報告 |
巻: | 109 |
号: | 235 |
開始ページ: | 35 |
終了ページ: | 40 |
論文番号: | COMP2009-37 |
抄録: | 安定結婚問題で不完全希望リストを許すと, 同じ例題に対する全ての安定マッチングは同サイズになる.しかし, 安定性を無視すると, 一般にはそれよりも大きなサイズのマッチングが存在する.Biroらは, 最大サイズのマッチングの中で出来るだけブロッキングペア数の少ないマッチングを求める問題を提案した.彼らは, (i)この問題がNP困難であり, 任意の正定数εに対してP≠NPの仮定の下でn^<1-ε>-近似アルゴリズムを持たないこと(nは例題中の男性の数), (ii)希望リストの長さを3以下に制限してもNP困難であり, ある定数δ>1が存在しP≠NPの仮定の下でδ-近似アルゴリズムを持たないこと, (iii)片側の性(例えば男性)の希望リストの長さが全て2以下ならば多項式時間で解けること, を示した.本論文では, 上記(ii)の近似不可能性を, 定数δからn^<1-ε>(εは任意の正定数)へと改良した. In the stable marriage problem that allows incomplete preference lists, all stable matchings for a given instance have the same size. However, if we ignore the stability, there can be larger matchings. Biro et al. defined the problem of finding a maximum cardinality matching that contains minimum number of blocking pairs. They proved that (i) this problem is NP-hard and cannot be approximated within the ratio of n^<1-ε> for any constant ε>0 unless P=NP, where n is the number of men in an input, (ii) even if each preference list is of length at most 3, the problem remains NP-hard and there exists a constant δ(>1) such that this problem cannot be approximated within the ratio of δ unless P=NP, and (iii) if the length of preference lists of one sex is at most 2, this problem is solvable in polynomial time. In this paper, we improve the constant δ of (ii) to n^<1-ε> for any ε>0. |
記述: | <コンピュテーション研究会(COMP)> 2009年10月16日(金) 10:00 - 16:35, 東北大学 青葉山キャンパス 電子情報システム・応物系 南講義棟103講義室 |
著作権等: | ©2009 by IEICE |
URI: | http://hdl.handle.net/2433/227006 |
関連リンク: | http://www.ieice.org/ken/paper/20091016xaQr/ |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。