歴代受賞者一覧

受賞者紹介
岩田 覚(いわた さとる)
昭和43年11月15日生まれ
東京大学大学院情報理工学系研究科数理情報学専攻 助教授

離散最適化における劣モジュラ関数最小化アルゴリズムの開発

岩田氏は離散最適化アルゴリズムの設計と解析に関する研究と、離散システムの構造理論、大規模システムの解析や制御への離散的手法の応用研究の分野で、国際的評価の高い論文誌に多くの論文を発表しており、高い評価を受けてきている。中でも顕著な業績は、劣モジュラ関数最小化の組合わせ的アルゴリズムの開発である。
劣モジュラ関数とは、有限集合の部分集合全体の上で定義された関数fで、 任意の部分集合X、Y に対して不等式

f(X)+f(Y) f(XUY)+f(XY)

を満たすものを指す。例えば、 ネットワークの容量関数や多端子情報源のエントロピー関数が劣モジュラ関数である。

凸関数の最小化が数値最適化において基本的であるのと同様に、劣モジュラ関数の最小化は離散最適化において基本的である。原理的にはすべての部分集合を列挙することによって劣モジュラ関数の最小値を計算できるが、列挙すべき部分集合の個数が莫大なので、このような素朴な方法は現実的でない。そこで、 対象となる離散システムの構造を有効に利用した効率的なアルゴリズムの設計が必要となる。

劣モジュラ関数最小化のアルゴリズムに関する研究は1980年頃に開始された。Grötschel、Lovász、 Schrijver(1981)が楕円体法を用いて、劣モジュラ関数最小化の最初の多項式時間アルゴリズムを設計した。楕円体法は収束が遅く、実際上の効率は極めて悪い。Cunningham(1985)が組合わせ的な擬多項式時間アルゴリズムを発表したが、それ以来、大きな進展は見られず、劣モジュラ関数最小化に対する組合せ的強多項式時間アルゴリズムの設計は、離散最適化における最も重要な未解決問題と言われ続けてきた。1999年に岩田氏を始めとするグループとA. Schrijver が独立に組合せ的強多項式時間アルゴリズムの開発に成功した。これらのアルゴリズムは乗除算を含んでいるので、加減算と大小比較のみを用いた組合せ的な強多項式時間アルゴリズムの設計が新たな課題となったが、これに対しても、岩田氏が肯定的な解決を与えた。この結果は、 劣モジュラ関数最小化問題に対する理論面での最終的な解答と位置付けられている。これにより、離散最適化における一つの大きな柱が確立されたことになる。さらに、待ち行列の制御や多元情報源の圧縮などの工学的問題が劣モジュラ関数最小化に帰着されることから、岩田氏の研究成果は数理工学全般にも貢献すると期待されている。

※所属名および役職は、受賞時のものです。