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

稳定匹配在各种分配问题中的应用

基本信息

批准号：
17700015
负责人：
宮崎修一
金额：
$ 2.24万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2005
资助国家：
日本
起止时间：
2005 至 2007
项目状态：
已结题

项目摘要

例えば大学の研究室配属において、各学生が研究室を志望順に順位付けし、同様に各研究室が学生を順位付けし、それらの希望に基づいて「安定条件」を満たす配属を求める問題を安定結婚問題という。この問題は、特に病院に研修医を配属することに応用されており、日本でも最近、研修医配属に本問題を利用し始めたことで、注目を集めている。本年度は以下の結果を得た。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)で発表した。

例如，在分配大学实验室时，每个学生按照偏好顺序对实验室进行排名，同样，每个实验室对学生进行排名，并根据这些偏好，找到满足“稳定性条件”的安置问题稳定下来就叫婚姻问题。这个问题特别适用于医疗实习生到医院的派遣，最近在日本的医疗实习生派遣中开始使用，引起了关注。今年，我们取得了以下成果。 1. 如果愿望列表中允许存在平局和不完整，则找到最大尺寸的稳定匹配的问题是 NP 困难的。在这项研究中，我们完成了1.875近似算法，并在去年的2007年ACM-SIAM离散算法研讨会（SODA）上公布，但今年我们将结果改进到1.8，完成了证明，并在国际上发表发表。 2.寻求稳定匹配的简单算法具有在见习医生侧或医院侧以有利的方式工作的特征。找到双方尽可能平等的稳定匹配的问题是NP困难的。在这项研究中，我们开发了一种多项式时间近似算法，并开发了一种根据给定参数找到尽可能接近最优解的算法。结果在 2007 年算法和数据结构研讨会 (WADS 2007) 上公布。 3、稳定室友问题是稳定婚姻问题的延伸，是2n个学生被分配到n个双人房间的问题，具有构建国际象棋比赛匹配组合等应用。在本研究中，我们将这个问题扩展到三人房间版本，并证明了近似的难度。这一结果在 2007 年韩国-日本算法与计算联合研讨会 (WAAC 2007) 上发表。