最大サイズ最大安定度マッチング問題に対する近似下限の改良

Abstract

安定結婚問題で不完全希望リストを許すと, 同じ例題に対する全ての安定マッチングは同サイズになる.しかし, 安定性を無視すると, 一般にはそれよりも大きなサイズのマッチングが存在する.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.