Read/Search this Article
Abstract
安定結婚問題において, 同順位リストと不完全リストの存在を許した問題に対して最大サイズの安定マッチングを見つける問題を考える.この問題はNP困難であり, 現在知られている最良の近似アルゴリズムは, (2-c (logN)/N)-近似アルゴリズムである.(ここで, cは任意の正定数であり, Nは入力中の男性の数である.)本論文では, この近似度を2-c 1/(N^<2/3>)に改良した.(cはc≦1/(2(√^3<6>)))を満たす正定数である.
We consider the problem of finding a stable matching of maximum size when both ties and unacceptable partners are allowed in preference lists. This problem is NP-hard and the current best known approximation algorithm achieves the approximation ratio 2-c (logN)/N, where c is an arbitrary positive constant and N is the number of men in an input. In this paper, we improve the ratio to 2-c 1/(N^<2/3>), where c is a constant such that c≦1/(2(√^3<6>)).
Journal
- IEICE technical report. Theoretical foundations of Computing [List of Volumes]
-
IEICE technical report. Theoretical foundations of Computing 105(72), 45-51, 2005-05-13 [Table of Contents]
The Institute of Electronics, Information and Communication Engineers
