各種配属問題への安定マッチングの応用

点击翻译按钮获取中文摘要

例えば大学の研究室配属において、各学生が研究室を志望順に順位付けし、同様に各研究室が学生を順位付けし、それらの希望に基づいて「安定条件」を満たす配属を求める問題を安定結婚問題という。この問題は、特に病院に研修医を配属することに応用されており、日本でも最近、研修医配属に本問題を利用し始めたことで、注目を集めている。本年度は以下の結果を得た。1.希望リストに同順位と不完全性を許した場合に、最大サイズの安定マッチングを求める問題はNP困難である。本研究では1.875-近似アルゴリズムを完成させ、昨年度の2007年のACM-SIAM Symposium on Discrete Algorithms(SODA)で発表したが、今年度はその結果を1.8まで改良し、証明を完成させ国際論文誌へ投稿した。2.安定マッチングを求める単純なアルゴリズムは、研修医側または病院側に優位に働くという特徴がある。できるだけ両者に平等な安定マッチングを求める問題はNP困難である。本研究では、多項式時間近似アルゴリズムの開発を行い、与えたパラメータに依存していくらでも最適に近い解を求めるアルゴリズムを開発した。この結果は、2007年のWorkshop on Algorithms and Data Structures(WADS 2007)で発表した。3.安定ルームメイト問題は、安定結婚問題の拡張であり、2n人の学生をn室の2人部屋へ配属させる問題であり、チェストーナメントの対戦組合せ構築などに応用がある。本研究では、この問題を3人部屋版に拡張し、その近似困難性を示した。この結果は2007年のKOREA-JAPAN Joint Workshop on Algorithms and Computation(WAAC 2007)で発表した。