藤重 悟

名前 藤重 悟 (Fujishige, Satoru)
名誉教授
E-Mail fujishig (emailアドレスには@kurims.kyoto-u.ac.jp をつけてください)
研究内容 離散最適化の研究
紹 介
 グラフ・ネットワーク・マトロイドなどの離散構造を有するシステムの 最適化について,劣モジュラ構造の観点からの研究を進めている(著書[B]参照)。
 平成22年度の研究に関わる主な研究内容は以下の通りである。
 劣モジュラ関数最小化アルゴリズムの理論的研究並びに効率的アルゴリズムの 実用化の研究を進めている。劣モジュラ関数によって定まる基多面体の 各端点にはその接錐に付随するネットワーク構造があり, これに注目することによって,凸結合のような数値的で線形代数的な操作を 必要としない``真に''組合せ的な劣モジュラ関数最小化アルゴリズムの 構成を目指している。 一方,劣モジュラ関数最小化の観点から提案した ``組合せ包''の概念の有効性についても 吟味し,その理論的な構造解明を進めている。
 また,線形計画問題のゾノトープ・モデルに基づく効率的 アルゴリズムとして LP-ニュートン法を提案し,その実装を進めると共に, 線形計画問題に対する強多項式時間アルゴリズムの 構成に向けて理論的研究を継続している。
 さらに, グラフの凸性に注目した枝素な有向木族のパッキングの問題から点素な問題への展開, 並びに,枝素な有向木族の根の最適配置問題の研究も行なっている。

[B] S. Fujishige: Submodular Functions and Optimization Second Edition (Annals of Discrete Mathematics, Vol. 58) (Elsevier, 2005).
[1] S. Fujishige and S. Isotani: A submodular function minimization algorithm based on the minimum-norm base. Pacific Journal of Optimization 7 (2011) 3--17.
[2] S. Fujishige: A note on disjoint arborescences. Combinatorica 30(2) (2010) 247--252.