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

このアイテムのファイル:
ファイル 記述 サイズフォーマット 
IEICE_tec.rep_COMP2004-8.pdf2.1 MBAdobe PDF見る/開く
タイトル: 局所探索法による安定結婚問題の近似
その他のタイトル: Approximating the Stable Marriage Problem by Local Search
著者: 岡本, 和也  KAKEN_name
宮崎, 修一  kyouindb  KAKEN_id
岩間, 一雄  KAKEN_name
著者名の別形: Okamoto, Kazuya
Miyazaki, Shuichi
Iwama, Kazuo
キーワード: 安定結婚問題
不完全リスト
同順位
近似アルゴリズム
局所探索法
the stable marriage problem
incomplete lists
ties
approximation algorithms
local search
発行日: 15-Apr-2004
出版者: 電子情報通信学会
誌名: 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報
巻: 104
号: 16
開始ページ: 53
終了ページ: 60
論文番号: COMP2004-8
抄録: 安定結婚問題の例題では、各個人の希望リストは異性全員を含み、完全に順位付けされている必要がある。しかし、実世界での応用を考えると、ペアになりたくない相手は希望リストに書かない不完全リストや、好みが同じ程度の人は優劣をつけなくて良い同順位リストという2つの自然な拡張が考えられる。どちらか一方の拡張のみを許した問題は多項式時間で解くことができるが、両方の拡張を許した場合、最大サイズの安定マツチングを見つける問題はNP困難になることが知られている。任意の2つの安定マッチングのサイズは最大でも2倍しか異ならないということは簡単にわかるため、近似度が2の近似アルゴリズムは自明である。2よりも良い近似度を実現する近似アルゴリズムを与える結果はいくつか知られているが、それらは、例えば同順位の長さや出現数などの制限を加えられた下でのものだけである。現在まで一般的な入力に対し、近似度が2未満となる近似アルゴリズムは知られていない。本論文では、一般的な例題に対し、近似度が2未満となる非自明な結果を初めて示した。我々のアルゴリズムの近似度は2-c(log N)/Nである。(ここで、cは任意の正定数で、Nは入力中の男性の数である。)
An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both of these variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two. and so, an approximation algorithm with a factor two is trivial. There are several contributions that give approximation algorithms with factor better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio 2-c(log N)/N for an arbitrarily positive constant c, where N denotes the number of men in an input.
著作権等: © 2004 電子情報通信学会(IEICE)
URI: http://hdl.handle.net/2433/227133
関連リンク: http://db.ieice.org/gakkai/show.php?id=155670
出現コレクション:学術雑誌掲載論文等

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

Export to RefWorks


出力フォーマット 


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