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

Abstract

安定結婚問題の例題では、各個人の希望リストは異性全員を含み、完全に順位付けされている必要がある。しかし、実世界での応用を考えると、ペアになりたくない相手は希望リストに書かない不完全リストや、好みが同じ程度の人は優劣をつけなくて良い同順位リストという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.