所員 -岩田 覚-

名前 岩田 覚 (Iwata, Satoru)
教授
E-Mail iwata (emailアドレスには@kurims.kyoto-u.ac.jp をつけてください)
研究内容 離散最適化の研究
紹 介
 離散最適化問題の中には,その構造を利用して効率的に解くことのできる問題と, 効率的な厳密解法の開発は本質的に無理であろうと考えられている問題とがある。 実用上有用な多くの離散最適化問題が,NP困難と呼ばれる後者の部類に属するとはいえ, 効率的に解くことのできる問題の構造を知ることは,計算困難な問題に対する現実的な 対処法を探る際の道具としても重要である。
 効率的に解くことのできる離散最適化問題に共通の構造として,劣モジュラ関数の重要性が J. Edmonds によって1970年に指摘されて以来,劣モジュラ関数に関連した最適化問題の研究が 続けられてきた。その中でも基本的な役割を果たす劣モジュラ関数の最小化に関して, 組合せ的な多項式時間アルゴリズムを与えた[1]。同時期に別の解法を開発した A. Schrijver によって, 乗除演算を用いずに,加減算と大小比較のみからなる完全に組合せ的な強多項式時間解法の存在が 問題提起されたが,論文[1]の解法に若干の技術的な工夫を加えることで,このようなアルゴリズムが 得られることが明らかになった[2]。また,論文[1]の解法に計算量の面での改良を加えた結果, より高速なアルゴリズムも得られている[5]。劣モジュラ関数最小化のアルゴリズムと他分野への 応用は,論文[7]で概説している。
 劣モジュラ集合関数が凸関数の離散版と看做せることは,1980年代前半に,L. Lov\'aszによって 指摘された。これを出発点として,整数格子点上の関数の離散凸性を考察した離散凸解析の理論が, 1990年代後半以降,室田によって展開されている。その主要な結果の一つが,Fenchel型双対定理であるが, この最大最小定理の両辺の最適解を計算する多項式時間解法を与えた[3]。さらに,容量スケーリング法を 用いて,より直接的で効率的なアルゴリズムも開発している[6]。
 劣モジュラ関数や離散凸解析の理論によって,効率的に解くことのできる多くの離散最適化問題が説明されるが, 同時に,これらの枠組みの範疇外にも効率的に解くことのできる離散最適化問題がある。最も代表的で, 興味深いのは,一般グラフのマッチングであろう。マッチング問題をマトロイドと結びつけて理解するために, マトロイド・パリティ問題と呼ばれる枠組みが1970年代に導入された。マトロイド・パリティ問題に関しては, 一般のマトロイド上では多項式時間が存在し得ないと同時に,線形表現されたマトロイドに対しては, 最大最小定理が成立し,多項式時間解法が存在することが L. Lovászによって示された。このような 興味深い現象が起こる背景に関して,まだ十分に理解されているとは言い難い状況にあり,重み付き線形 マトロイド・パリティ問題に対する多項式時間解法の開発を始めとして,解決すべき課題が残されている。
 マトロイドを一般化したデルタ・マトロイドの概念は,1980年代後半に A. Bouchet等によって導入された。 論文[4]では,歪対称行列で表現される線形デルタ・マトロイドに対するパリティ問題を導入し, 最大最小定理と多項式時間解法とを提示した。 以上のような離散最適化手法の研究と併行して,動的システムのモデル化への応用を研究している。 特に,混合解析と呼ばれる回路解析法において,微分代数方程式の数値的な解き難さを表す指数が 最小となるように変数を選択する効率的な方法を与えた[8,9]。また,干渉効果を考慮した無線通信の モデルとして最近提案されたADTモデルにおいて,劣モジュラ関数最小化と高速Fourier変換(FFT)を 利用して最大流量を計算する効率的なアルゴリズムを開発した。[10]
  1. A combinatorial strongly polynomial algorithm for minimizing submodular functions, J. ACM, 48 (2001), 761--777. (with L. Fleischer and S. Fujishige)
  2. A fully combinatorial algorithm for submodular function minimization, J. Combin. Theory, B84 (2002), 203--211.
  3. Conjugate scaling algorithm for Fenchel-type duality in discrete convex optimization, SIAM J. Optim., 13 (2003), 204--211. (with M. Shigeno)
  4. The linear delta-matroid parity problem, J. Combin. Theory, B88 (2003), 377--398. (with J. F. Geelen and K. Murota)
  5. A faster scaling algorithm for minimizing submodular functions, SIAM J. Comput., 32 (2003), 833--840.
  6. A capacity scaling algorithm for M-convex submodular flow, Math. Programming, 103 (2005), 181--202. (with S. Moriguchi and K. Murota)
  7. Submodular function minimization, Math. Programming, 112 (2008), 45--64.
  8. Index minimization of differential-algebraic equations in hybrid analysis for circuit simulation, Math. Programming, 121 (2010), 105--121. (with M. Takamatsu)
  9. Tractability index of hybrid equations for circuit simulation, Math. Comput., 81 (2012), 923--939. (with M. Takamatsu and C. Tischendorf)
  10. A flow model based on polylinking systems, Math. Programming, to appear. (with M. X. Goemans and R. Zenklusen)