Extensions of stable matching problems and algorithm design

異なる2つのグループの各メンバーが他方のグループのメンバーに対する選好順序を持っているとき、この選好順序に基づいた「安定性」と呼ばれる性質を満たすマッチングを安定マッチングという。本研究の目的は、安定マッチングを実用に即して拡張し、それらのモデルに対する計算複雑性を明らかにすることである。本年度は以下の活動を行った。(1) 病院の研修医配属問題において、各病院が定員下限を宣言するモデルはこれまでに複数研究されている。本研究では定員充足率を最大化する問題を定式化し、幾つかの場合に対してアルゴリズムの設計と解析、計算複雑性の結果を得、昨年度末に査読付き国際会議STACS 2022にて発表していた。本年度はこの継続として、希望リストが不完全（すなわち、他方のグループのメンバー全員を書かなくて良い）という一般化に対する研究を行い、同じくアルゴリズム設計や計算複雑性解析を行った。本結果は、査読付き国際会議SAGT 2022にて発表した。(2) 研修医配属問題において医師の都市部集中を抑制するため、幾つかの病院をまとめた「地域」を定義し、各地域に上限を設定する問題が提案されており、この問題のNP完全性が最近示されていた。本研究では、希望リストの長さや地域のサイズなどをパラメータとして、問題がNP完全となる場合と多項式時間で解ける場合の境界を明らかにした。この結果は昨年度に国内の無審査研究会で発表していたが、本年度は査読付き国際会議COCOON 2022に採録され発表した。(3) 安定マッチングに関するこれまでの研究成果を産業界および一般に周知するため、ひょうご講座2022、兵庫県立大学 知の交流シンポジウム2022、兵庫県立大学オープンキャンパス ミニ模擬授業、兵庫県立大学附属中学校中大連携授業での講演に、安定マッチングの話題を取り入れた。

異なる2つのグループの各メンバーが他方のグループのメンバーに対する選好順序を持っているとき、この選好順序に基づいた「安定性」と呼ばれる性質を満たすマッチングを安定マッチングという。本研究の目的は、安定マッチングを実用に即して拡張し、それらのモデルに対する計算複雑性を明らかにすることである。本年度は以下の活動を行った。(1) 病院の研修医配属問題において、各病院が定員下限を宣言するモデルはこれまでに複数研究されている。本研究では定員充足率を最大化する問題を定式化し、幾つかの場合に対してアルゴリズムの設計と解析、計算複雑性の結果を得、昨年度末に査読付き国際会議STACS 2022にて発表していた。本年度はこの継続として、希望リストが不完全（すなわち、他方のグループのメンバー全員を書かなくて良い）という一般化に対する研究を行い、同じくアルゴリズム設計や計算複雑性解析を行った。本結果は、査読付き国際会議SAGT 2022にて発表した。(2) 研修医配属問題において医師の都市部集中を抑制するため、幾つかの病院をまとめた「地域」を定義し、各地域に上限を設定する問題が提案されており、この問題のNP完全性が最近示されていた。本研究では、希望リストの長さや地域のサイズなどをパラメータとして、問題がNP完全となる場合と多項式時間で解ける場合の境界を明らかにした。この結果は昨年度に国内の無審査研究会で発表していたが、本年度は査読付き国際会議COCOON 2022に採録され発表した。(3) 安定マッチングに関するこれまでの研究成果を産業界および一般に周知するため、ひょうご講座2022、兵庫県立大学 知の交流シンポジウム2022、兵庫県立大学オープンキャンパス ミニ模擬授業、兵庫県立大学附属中学校中大連携授業での講演に、安定マッチングの話題を取り入れた。