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 (ⅰ) 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, (ⅱ) even if each preference list is of length at most 3, the problem remains NP-hard and there exists a constant δ5(> 1) such that this problem cannot be approximated within the ratio of δ unless P=NP, and (ⅲ) 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 5 of (ⅱ) to n~(1-ε) for any ε > 0.%安定結婚問題で不完全希望リストを許すと，同じ例題に対する全ての安定マッチングは同サイズになる．しかし，安定性を無視すると，一般にはそれよりも大きなサイズのマッチングが存在する．Birdらは，最大サイズのマッチングの中で出来るだけブロッキングペア数の少ないマッチングを求める問題を提案した．彼らは，（i）この間題がNP 困難であり，任意の正定数どに対してP‡NP の仮定の下でn~(1-ε)一近似アルゴリズムを持たないこと（n は例題中の男性の数），（ii）希望リストの長さを3以下に制限してもNP 困難であり，ある定数δ＞1が存在しP‡NP の仮定の下でδ-近似アルゴリズムを持たないこと，（iii）片側の性（例えば男性）の希望リストの長さが全て2以下ならば多項式時間で解けること，を示した．本論文では，上記（ii）の近似不可能性を，定数δかられ1~(1-ε)（εは任意の正定数）へと改良した．
展开▼
