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

点击翻译按钮获取中文摘要

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