安定マッチング問題の複雑さに関する研究

稳定匹配问题的复杂性研究

基本信息

批准号：
07J04017
负责人：
岡本和也
金额：
$ 1.15万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2007
资助国家：
日本
起止时间：
2007 至 2008
项目状态：
已结题

项目摘要

安定マッチング問題の1つである安定ルームメイト問題は交換腎移植手術のための患者・ドナー間のマッチングという応用が存在する。そのため、安定ルームメイト問題は重要な問題であると考えられ、盛んに研究がなされている。我々は、安定ルームメイト問題を拡張し、3次元安定ルームメイト問題を提唱した。そして、3次元安定ルームメイト問題の近似困難性を示した。また、幾何的安定ルームメイト問題を提唱し、安定ルームメイト問題との差異を示した。この差異とは全ての例題において解が存在するということとアルゴリズムの高速化が可能であるといった良い性質であり、交換腎移植手術にも応用できる自然な拡張であることから、今後の応用が期待される。また、我々はグラフのCentralityの1種であるCloseness Centralityを扱い、Closeness Centralityの高い節点を効果的にランキングするアルゴリズムを開発した。このアルゴリズムは既存の近似アルゴリズムと厳密アルゴリズムを効率良く組み合わせたもので、これまでのアルゴリズムよりも高速に動作することを示した。このCentralityに基づく節点のランキングアルゴリズムは萌芽的な研究であり、今後さらなる発展が期待される。さらに、携帯電話技術の1つである3Gに応用されるオンラインOVSF符号割当問題を扱った。我々は、これまで知られていたオンラインアルゴリズムよりも競合比という観点の下で、性能の良いオンラインアルゴリズムを開発し、これまで知られていた競合比の下限を改良した。

稳定室友问题是稳定匹配问题之一，在交换肾移植手术的患者和捐献者匹配中具有应用前景。因此，稳定的室友问题被认为是一个重要问题并正在积极研究。我们扩展了稳定室友问题，提出了三维稳定室友问题。我们还证明了近似三维稳定室友问题的难度。我们还提出了几何稳定室友问题，并展示了它与稳定室友问题的区别。这种差异具有所有示例问题都存在解以及加速算法的可能性等良好性质，是可以应用于交换肾移植手术的自然延伸，因此预计它将应用于未来。我们还开发了一种处理 Closeness Centrality（图中心性的一种）的算法，并有效地对具有高 Closeness Centrality 的节点进行排名。该算法是现有近似算法和精确算法的有效组合，并且已被证明比以前的算法运行速度更快。这种基于Centrality的节点排序算法是一项探索性研究，预计未来会得到进一步发展。此外，我们还解决了应用于3G（移动电话技术之一）的在线OVSF代码分配问题。我们开发了一种在线算法，在竞争比方面比以前已知的在线算法表现更好，并提高了以前已知竞争比的下限。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

オンラインOVSF符号割当問題における競合比の上下限の改良

在线OVSF代码分配问题竞争比上下界的改进

DOI：
发表时间：
2009
期刊：
影响因子：
0
作者：
岡本和也; 宮崎修一
通讯作者：
宮崎修一

Improved Upper Bounds on the Competitive Ratio for Online Realtime Scheduling

提高在线实时调度竞争力的上限

DOI：
10.1007/978-3-540-75520-3_42
发表时间：
2007-10-08
期刊：
IEEE Transactions on Information Theory
影响因子：
2.5
作者：
Koji M. Kobayashi;K. Okamoto
通讯作者：
K. Okamoto

Geometric stable roommates

几何稳定的室友

DOI：
发表时间：
2009
期刊：
影响因子：
0
作者：
Esther M. Arkin; Sang Won Bae; Alon Efrat; Kazuya Okamoto; Joseph S. B. Mitchell; Valentin Polishchuk
通讯作者：
Valentin Polishchuk

Recent Development of Approximation Algorithms for General Stable Marriage

一般稳定婚姻近似算法的最新进展