岩政いわまさ 勇仁ゆに

東京大学大学院 情報理工学系研究科 数理情報学専攻 数理情報第2研究室 博士課程

指導教員:平井 広志 准教授

〒113-8656 東京都文京区本郷7-3-1
東京大学大学院 情報理工学系研究科 数理情報学専攻
E-mail: yuni_iwamasa [at] mist.i.u-tokyo.ac.jp

研究分野

  • 組合せ最適化
  • 離散数学
  • 離散凸解析
  • 値付き制約充足問題 (Valued Constraint Satisfaction Problem; VCSP)

研究内容

組合せ最適化・離散最適化の研究をしています.とくに,

  • 問題の数理的構造を利用した多項式時間アルゴリズムの構築
  • 多項式時間で解ける問題の背後にある数理的構造の解明
  • 多項式時間で解ける問題と解けない(or 解けなさそうな)問題の分類
に興味があります.

主に,値付き制約充足問題 (Valued Constraint Satisfaction Problem; VCSP)離散凸解析の研究を行っています.

VCSP とは,変数の個数が少ない(e.g., 2 変数や 3 変数)関数の和で表される多変数関数の最小化問題を扱う離散最適化の枠組みです.非常に多くの離散最適化問題を定式化できる汎用的なものなのですが,その汎用性ゆえ,VCSP は一般的には NP-hard です.この分野の主目的は「どんな問題クラスが多項式時間で解けるかを解明する」ことです.

離散凸解析とは,整数格子点上に定義された凸関数に関する理論です.劣モジュラ性を拡張した概念であるL凸性とマトロイドを拡張した概念であるM凸性を軸に理論が展開されており,これらの凸性は,多項式時間で解ける様々な問題の背後にある数理的な構造として現れています.

最近は,VCSP に対して離散凸解析の理論を適用して,新たな多項式時間可解な問題クラスを構築する研究を行っています.

また,離散凸解析理論の拡張やその実社会への応用にも興味があります.