多様な局面に適合した安足マッチング問題の解法研究

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

安定結婚問題とは、2つの異なるグループ間で、希望順位に基づき「安定」なマッチングを求める問題である。アメリカやカナダなどでは、研修医の病院配属に古くからこの問題が利用されていたが、日本でも平成15年度から病院配属に利用され始めた。本研究の目的は、安定結婚問題を日本の研修医配属に利用する際の問題点を考え、それを解決することである。本年度は、以下の2点について成果を挙げた。希望リストに同順位や不完全リストを許すと、最大サイズの安定マッチングを求める問題はNP困難になり、多項式時間では最適解が求められそうにない。そのため、出来るだけ大きなサイズのマッチングを多項式時間で求める、いわゆる近似アルゴリズムの開発が重要となる。これまでは、近似度2のアルゴリズム(すなわち、最大サイズの半分の大きさを保証するアルゴリズム)が最良であった。本研究では、近似度2-0(N/logN)のアルゴリズムの開発に成功した。(SWAT2004)ここで、Nは例題中の男性(または女性)の数である。また、それを改良したアルゴリズムの開発にも成功し、現在国際学会に投稿中である。1つの例題が最大いくつの安定マッチングを持ちうるかという問題は、数学的興味、および、実用の面からも重要な問題である。本研究では、サイズNの例題の持ちうる安定マッチング数について、上限、下限ともに改良した。この結果は未発表であり、現在学会投稿を検討中である。