Research on Formalization and Algorithms for the Stable Matching Problems Adapted to Real World

适应现实世界的稳定匹配问题的形式化和算法研究

• 批准号: 20700009
• 负责人: MIYAZAKI Shuichi
• 金额: $ 2.75万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20700009/
• 关键词: アルゴリズム; 組み合わせ問題; 最適化問題; 近似アルゴリズム; 安定マッチング; 研修医配属; 近似困難性; 安定マッチング問題; 研修医配属問題; 多項式時間アルゴリズム; Gale-shapleyアルゴリズム; NP困難性; 近似度; 組み合わせアルゴリズム; NP困難問題; Gale-Shapleyアルゴリズム; 整数計画問題; 線形計画緩和; 安定結婚問題; 最適化; 線形計画問題; 安定ルームメイト問題

In the stable matching problem, each person submits a list that orders members of the opposite gender based on his/her preference. The task is to find a matching with property called the stability. This problem can be applied to many real-world assignment problem, such as assigning residents to hospitals. In this research, we proposed several variants of this problem to adapt it to each occasion. We also proposed efficient algorithms for them, as well as proved some intractability and inapproximability.

在稳定匹配问题中，每个人提交一个列表，根据他/她的偏好对异性成员进行排序。任务是找到一个匹配的属性称为稳定性。这个问题可以应用到现实世界中的许多分配问题，如分配居民到医院。在这项研究中，我们提出了这个问题的几个变体，以适应各种场合。我们还提出了有效的算法，以及证明了一些棘手的和不可逼近的。

项目成果

2部グラフ上での分担供給可能な割当て制限付き資源配分問題

具有配额约束的资源分配问题，可以在二分图上共享和提供

• 发表时间: 2010
• 作者: 森本尚之;宮崎修一;岡部寿男
• 通讯作者: 岡部寿男

段階的秘密交換プロトコルを利用した配達内容証明が可能な電子メールプロトコルの設計上の検討

允许使用逐步秘密交换协议进行传递证明的电子邮件协议的设计注意事项

• 发表时间: 2008
• 作者: 清水敬太;宮崎修一;岡部寿男
• 通讯作者: 岡部寿男

離散数学のすすめ 第17章「安定結婚問題」

离散数学导论第17章“稳定婚姻问题”

• 发表时间: 2010
• 作者: 白川理香;三村達哉;臼井智彦;本田紀彦;福岡詩麻;天野史郎;宮崎修一(分担)
• 通讯作者: 宮崎修一(分担)

A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties

一种解决单边关系稳定婚姻问题的 25/17 近似算法

• DOI: 10.1007/s00453-012-9699-2
• 发表时间: 2014
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Kazuo Iwama;Shuichi Miyazaki;and Hiroki Yanagisawa
• 通讯作者: and Hiroki Yanagisawa

2ポートマルチキュースイッチにおける最適なオンラインバッファ管理アルゴリズム

2端口多队列交换机在线缓冲区优化管理算法

• 发表时间: 2008
• 作者: 小林浩二;宮崎修一;岡部寿勇
• 通讯作者: 岡部寿勇