Scaling and proximity properties of discrete optimization

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

本研究は，離散最適化に対して，スケーリング技法を軸とするアルゴリズム効率化のための理論体系を構築することを目的とし，また理論の応用を見据えて，研究を推進した．スケーリングとは，定義域の偶数点のみを見る，などのように，目盛を間引いた関数近似の導入で効率化を図る技法で，古典的なネットワークフローや資源配分問題で多くの成功例が知られている．離散凸解析のこれまでの研究により，いくつかの離散凸関数最小化に対して，スケーリング技法の有効性と近接定理による理論保証が明らかになっている．本研究では，これまでスケーリング技法や近接定理について考えられていなかったより広い離散関数のクラスに対する拡張と理論構築を試み，効率的なアルゴリズムが構築可能なクラスの解明を進めていった．離散凸最適化においては，Ｍ凸関数，Ｌ凸関数，整凸関数，マルチモジュラ関数など，種々の関数クラスが考察される．それらの間の包含関係や，そのうちの２つのクラスの共通部分がどのようなものになるのかを，網羅的に整理した．これによって，様々な分野の研究者が離散凸関数の概念を容易に理解できるようになる．また，離散凸構造の多面体的表現を解明していった．複数の離散凸構造の間の包含関係や，そのうちの２つのクラスの共通部分の理解に，多面体的表現が有用であったことから始まった研究であるが，多面体的表現により，スケーリング，近接性に関する議論がしやすくなり，また整数計画の理論の応用やソルバーの利用がしやすくなるという今後の展開が開ける．