局所構造を利用した高速なアルゴリズムの開発

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

離散最適化分野で未解決であった劣モジュラコストをもつ4－分割問題に対する初めの多項式時間アルゴリズムを構築した。またこの論文で用いたアルゴリズムフレームワークでは、４より大きな個数に分割する問題は解けないことも示した。また、再配置問題においてはその問題の離散構造を明らかにするとともに、さまざまな自然な設定の下での多項式時間アルゴリズム、近似アルゴリズム、制約を緩和した精度を保証したアルゴリズムなどの構築に成功した。それ以外にも、１．k彩色遷移問題とは，無向グラフと二つのk彩色が与えられた際に，k彩色であるという条件を保ったまま一度に一つの頂点の色を(局所的に)変更し，一方の彩色から他方の彩色へ変換することができるか否かを判定する問題である．本研究では，遷移制約をもつk彩色遷移問題を扱い，遷移制約が有向サイクルや特殊なマルチツリーで与えられる場合に，同問題が高速に(より正確には線形時間で)解けることを示した．２．ある特殊な整数計画問題に対し，解空間の局所的な構造について解析した．具体的には，整数解を求める問題を実数解を求める問題へ緩和した際に，緩和した問題の最適解の（局所的な）近傍に最適整数解が存在することを示した．これにより．この特殊な整数計画問題に対して，理論的に高速な分枝限定法（アルゴリズム）を開発した．