安定結婚問題に対する局所探索近似アルゴリズムの改良

摘要

安定結婚問題において，同順位リストと不完全リストの存在を許した問題に対して最大サイズの安定マッチングを見つける問題を考える．この問題はNP困難であり，現在知られている最良の近似アルゴリズムは，(2-c(logN)/N)－近似アルゴリズムである．（ここで，cは任意の正定数であり，Nは入力中の男性の数である．）本論文では，この近似度を2-c(1/(N{sup}(2/3)))に改良した．（cはc≦1/(2(6{sup}(1/3)))を満たす正定数である．）