研究概要

パラメータ化アルゴリズム,近似アルゴリズム,遷移アルゴリズムなど,多様なアプローチを駆使し,NP困難な組合せ最適化問題に対するスケーラブルな解法を探求しています.理論的な性能保証と,実世界の大規模インスタンスを扱える実用的な計算速度との両立を目指している点が本テーマの特徴です.理論研究の成果は,企業との共同研究を通して社会実装にも繋がっています.

頂点被覆問題の例で,全探索では約290兆年かかる計算が,有界探索木なら約0.005秒で終わることを示す図

研究テーマ

パラメータ化計算複雑性に基づくアルゴリズム設計と解析

NP困難やPSPACE困難であることが知られている問題に対しても,問題の構造を捉える適切なパラメータに着目することで,現実的に効率の良いアルゴリズムを設計できる場合があります.こうした観点から,多様な組合せ問題に対するパラメータ化計算複雑性の精緻な解明に取り組んでいます.様々な構造パラメータの下での固定パラメータ容易性(FPT等)とW階層における困難性(W[1]-hard等)の境界を明らかにする研究を通して,問題の難しさの本質がどこにあるのかを見極めるとともに,それを乗り越えるアルゴリズム設計の指針を提供する取り組みとなっています.

近似アルゴリズムと近似困難性

NP困難な最適化問題では,最適解を現実的な時間で求めることは難しいと考えられています.そこで,最適解に近い解を多項式時間で求め,その精度を理論的に保証する近似アルゴリズムを設計するとともに,どの程度まで近い解を効率よく求められるのか,その限界を示す近似困難性の解析にも取り組んでいます.これまでに,グラフ上のトークン交換問題,ケンペ変更によるグラフ彩色の最短遷移問題,パスカバー問題の変種に対する近似アルゴリズムや,有向グラフ上の最小キャタピラー問題,色付きトークンの交換問題に対する近似困難性を示しています.

不確実な状況での逐次意思決定

問題の情報があらかじめ分かっていない状況では,試行を通して情報を集めながら判断を重ねる必要があります.本研究室では,限られた試行の中で最良の選択肢を見つける多腕バンディット問題や,強化学習における方策の検定などに取り組んでいます.広告配信のような応用も念頭に置きつつ,統計的な最適性を理論的に保証するアルゴリズムの設計を進めています.

関連する発表

研究紹介に戻る