研究テーマ

離散アルゴリズム研究室では，効率的な離散アルゴリズムについて研究しています．離散アルゴリズムとは，離散構造を持つ計算問題を単純な計算ステップの積み重ねで解くアルゴリズムのことです．離散構造を持つ計算問題は情報科学の至る所で現れます．我々はそのような計算問題に対して単純で性能の高い離散アルゴリズムを与えることで，効率的な意思決定を可能としたり、これまでにない高速で質の高い情報システムの実現を目指しています．

具体的な研究目標としては，次の３つを掲げています．

  • 普遍的な構造を持ち，解決することで計算理論や応用分野の広い範囲に大きなインパクトを与えることができる問題に対して，新たなアルゴリズムの開発や方法論を確立すること．
  • 人工知能，機械学習，データ解析などの領域で現れる離散的な最適化問題・計算問題をモデル化し，そのような問題を解く実用的なアルゴリズムを与えること．
  • 無線ネットワーク，センサー，クラウドコンピューティングなど，近年の情報通信技術の新しい技術を，新しいグラフ最適化問題として定式化し，グラフアルゴリズムや離散最適化における新たな潮流を作り出すこと．

これまでの研究成果

ネットワーク設計アルゴリズム

様々な制約を満たす低コストネットワークの形状を計算するネットワーク設計アルゴリズムの研究をしています．これまで多くの基礎的なネットワーク設計問題に対して，新たなアルゴリズムを与えることに成功しています．

例えば，頂点の欠損に強いネットワークを構築する頂点連結度ネットワーク設計問題に対しては，従来は適用が難しかった反復丸め法と呼ばれる手法を適用することに成功しました [Fukunaga, Nutov, Ravi 2015]．さらに，ネットワークアクティベーション問題については，スパイダー被覆アルゴリズムに対する線形計画問題に基づいた新たな解析を与えました。この解析により，問題を更に一般化した場合でもアルゴリズムが適用可能となりました [Fukunaga 2017]．そのほかには，一般化ターミナルバックアップ問題と呼ばれる，多項式時間アルゴリズムが存在するかNP困難か未解決な問題に対して，知られている中では最も最適化の精度が高いアルゴリズムを与えました [Fukunaga 2017]．

  • T. Fukunaga, Z. Nutov, R. Ravi: Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design. SIAM J. Comput. 44(5): 1202-1229 (2015)
  • Takuro Fukunaga: Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation. SIAM J. Discrete Math. 30(2): 777-800 (2016)
  • T. Fukunaga: Spider Covers for Prize-Collecting Network Activation Problem. ACM Trans. Algorithms 13(4): 49:1-49:31 (2017)

グラフ・ハイパーグラフのカット問題

グラフ（ネットワーク）を複数の成分に分割するグラフカット問題は，そのグラフの結びつきが脆弱な箇所を求める組合せ最適化問題です．組合せ最適化の歴史においても頻繁に研究されている基本問題であるだけでなく，画像処理やクラスタリングアルゴリズムの中でも利用されるなど多くの応用も持ちます．我々はこれまで，グラフカット問題や，より一般的なハイパーグラフカット問題・劣モジュラシステム分割問題に対する新しいアルゴリズムの開発しました [Okumoto, Fukunaga, Nagamochi 2012; Fukunaga 2013]．また，画像のセグメンテーションをモチベーションとして提案されたハイパーグラフ相関クラスタリングと呼ばれるカット問題に対し，新たなアルゴリズムも与えています [Fukunaga 2019]．これらのアルゴリズムのクラスタリングへの応用にも取り組んでいます [Hatano et al. 2017]．

  • K. Okumoto, T. Fukunaga, H. Nagamochi: Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems. Algorithmica 62(3-4): 787-806 (2012)
  • T. Fukunaga: Computing minimum multiway cuts in hypergraphs. Discrete Optimization 10(4): 371-382 (2013)
  • D. Hatano, T. Fukunaga, T. Maehara, K. Kawarabayashi: Scalable Algorithm for Higher-Order Co-Clustering via Random Sampling. AAAI 2017: 1992-1999
  • T. Fukunaga: LP-based pivoting algorithm for higher-order correlation clustering. J. Comb. Optim. 37(4): 1312-1326 (2019)

確率的組合せ最適化問題に対する適応的最適化アルゴリズム

数理最適化は様々な情報から数理的な手法を駆使して効率的な計画を立案するための技術ですが，実際に利用する際には確定的な情報が与えられることはまれです．そのような不確実な環境下で意思決定を行うために，適応的最適化の研究を行っています．適応的最適化では，計画の全てをあらかじめ決めるのではなく，計画の一部を決めて実行に移し，その結果得られた新たな情報に基づいて適応的に計画を調整します．我々は適応的最適化の理論基盤を構築するための研究とともに，産業や機械学習などの分野で現れる問題に対して適応的最適化を利用するための研究を行っています ．これまでに，不確実なナップサック制約を持つ劣モジュラ最大化問題や，パフォーマンスに依存するアイテムコストを持つ設定での確率的劣モジュラ最大化問題に対して適応的アルゴリズムを設計しました [Kawase, Sumita, Fukunaga, 2019; Fukunaga et al., 2019]．

  • Y. Kawase, H. Sumita, T. Fukunaga: Submodular Maximization with Uncertain Knapsack Capacity. SIAM J. Disc. Math. 2019.
  • T. Fukunaga, T. Konishi, S. Fujita, K. Kawarabayashi: Stochastic Submodular Maximization with Performance-Dependent Item Costs, AAAI 2019.

データセンターネットワークや無線アドホックネットワークにおけるグラフアルゴリズムの研究

通信ネットワークで発生する様々な課題をグラフ上の計算問題として定式化し，新たなアルゴリズムを与える研究を行っています．データセンターネットワークについては、データセンターの物理マシン上に仮想マシンを配置する際に，通信が発生する仮想マシンは近くに配置するような最適化問題を考え，アルゴリズムを与えました [Fukunaga, Hirahara, Yoshikawa, 2017]．また，災害現場などで利用が期待されている無線アドホックネットワークを運用する際に必要となるバックボーンネットワークの計算をモデル化した高連結支配集合問題に対して，新たなアルゴリズムを与えました [Fukunaga, 2018]．

  • T. Fukunaga, S.Hirahara, H. Yoshikawa: Virtual Machine Placement for Minimizing Connection Cost in Data Center Networks. Discrete Optimization 26: 183-198 (2017)
  • T. Fukunaga: Approximation Algorithms for Highly Connected Multi-dominating Sets in Unit Disk Graphs. Algorithmica 80(11): 3270-3292 (2018)