Extensions of stable matching problems and algorithm design

稳定匹配问题和算法设计的扩展

• 批准号: 20K11677
• 负责人: 宮崎 修一
• 金额: $ 2.83万
• 依托单位: University of Hyogo (2022)Kyoto University (2020-2021)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K11677/
• 关键词: 安定マッチング; アルゴリズム理論; 計算複雑性; 近似アルゴリズム; 研修医配属; 地域上限; 定員下限; 非交差安定マッチング; NP困難性; 例題生成; 希望リスト; 非交差マッチング; 配属システム; モデル化; 安定マッチング; アルゴリズム理論; 計算複雑性; 近似アルゴリズム; 研修医配属; 地域上限; 定員下限; 非交差安定マッチング; NP困難性; 例題生成; 希望リスト; 非交差マッチング; 配属システム; モデル化

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

当两个不同组的每个成员对另一组成员都有一个优先顺序时，根据此优先顺序满足“稳定性”属性的匹配称为稳定匹配。这项研究的目的是从实践中扩展稳定的匹配，并阐明这些模型的计算复杂性。今年，我们进行了以下活动：（1）到目前为止，已经对几种模型进行了研究，其中每个医院宣布医院居民发行的容量限制较低。这项研究提出了一个问题，该问题最大化了容量履行率，并从多种情况下从算法设计，分析和计算复杂性中获得了结果，并在去年年底在同行评审的国际STACS 2022中提出了示意。作为今年的延续，我们对愿望清单不完整的概括进行了研究（即，不必编写其他组的所有成员），还进行了算法设计和计算复杂性分析。结果是在经过同行评审的国际会议下SAGT 2022中介绍的。（2）为了抑制居住分配问题中城市地区医生的集中注意力，已经提出了一个问题，其中定义了一个“区域”，以结合多家医院并为每个地区设置一个CAP，并显示了这个问题的NP完整性。在这项研究中，我们使用参数（例如所需列表的长度和区域的大小），确定了问题变得完美的情况以及可以在多项式时间求解的情况之间的边界。 The results were presented at a domestic unexamined study group last year, but this year they were collected and presented at the peer-reviewed international conference COCOON 2022. (3) In order to make the results of previous research on stable matching known to the industry and the public, the topic of stable matching was incorporated into lectures at Hyogo Lectures 2022, Hyogo Prefectural University Knowledge Exchange Symposium 2022, Hyogo县校区开放式校园迷你模拟课程，以及诺戈郡郡大学初中初中合作班。