局所探索法による安定結婚問題の近似

概要

論文の詳細を見る
安定結婚問題の例題では、各個人の希望リストは異性全員を含み、完全に順位付けされている必要がある。しかし、実世界での応用を考えると、ペアになりたくない相手は希望リストに書かない不完全リストや、好みが同じ程度の人は優劣をつけなくて良い同順位リストという2つの自然な拡張が考えられる。どちらか一方の拡張のみを許した問題は多項式時間で解くことができるが、両方の拡張を許した場合、最大サイズの安定マツチングを見つける問題はNP困難になることが知られている。任意の2つの安定マッチングのサイズは最大でも2倍しか異ならないということは簡単にわかるため、近似度が2の近似アルゴリズムは自明である。2よりも良い近似度を実現する近似アルゴリズムを与える結果はいくつか知られているが、それらは、例えば同順位の長さや出現数などの制限を加えられた下でのものだけである。現在まで一般的な入力に対し、近似度が2未満となる近似アルゴリズムは知られていない。本論文では、一般的な例題に対し、近似度が2未満となる非自明な結果を初めて示した。我々のアルゴリズムの近似度は2-c(log N)/Nである。(ここで、cは任意の正定数で、Nは入力中の男性の数である。)
2004-04-15

局所探索法による安定結婚問題の近似

スポンサーリンク

概要

著者

関連論文

スポンサーリンク