豊橋技術科学大学

検索

Search

藤戸 敏弘(ふじと としひろ)

所属 情報・知能工学系
職名 教授
専門分野 アルゴリズム / 離散最適化 / 計算量
学位 Ph.D. (ペンシルバニア州立大学)
所属学会 電子情報通信学会 / 情報処理学会
E-mail fujito@cs
※アドレスの末尾に「.tut.ac.jp」を補完してください
研究室web http://www.algo.cs.tut.ac.jp/
研究者情報(researchmap) 研究者情報

研究紹介

実用上重要で、計算機で処理するのに適していながら、それを実際に計算するには膨大な計算量が必要となり、結果的に小規模な入力しか現実には処理できない問題(例えば、巡回セールスマン問題など)は、決して例外的に現れるのではなく、実社会にもひろく存在することが認められています。そこで、このような(NP困難とよばれる)問題の厳密解にどれだけ近い解を効率よく計算することが可能/不可能であるかを、アルゴリズム論の立場から研究しています。特に、個々の近似アルゴリズム設計にとどまらず、従来からの組合せ論や確率論にくわえて数理計画、多面体論などを利用した、汎用性のあるアルゴリズム技法の開発に興味があります。今後の抱負は、従来の枠組ではとらえらることができなかったNP困難問題にも対処できるようなアルゴリズムと計算量の理論の発展に貢献することです。

テーマ1:離散構造を持つ問題に対するアルゴリズムの理論的研究

概要

効率の良いアルゴリズムを設計するためには,その問題の持つ構造に合致したアルゴリズムの動作原理を見出す必要があります.多くの問題に共通に利用できる動作原理はアルゴリズムの設計手法としてその理論的枠組みが構築されてきています.計算量理論の観点と合わせて,問題の計算複雑度による分類も進んでいます.より最近では,厳密最適解を高速に求めることが困難とされているNP-困難な問題に対しても,精度が保証された近似最適解を高速に求めるアルゴリズムの設計手法が開発されています.ここでは,従来のアルゴリズム設計手法に加え,数理計画や確率論を動作原理に取り入れることで,新しいアルゴリズム設計手法が構築されつつあります.
これまで,集合やマトロイドの被覆/充填問題,グラフの頂点被覆問題,辺支配問題,帰還点集合問題,劣モジュラ被覆問題などに対し高速・高性能なアルゴリズムや設計手法を提案してきました.

主な業績:
◆ Bafna, V., Berman, P., Fujito, T. (1999)
A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem, SIAM J. Disc. Math., 12(3) 289-297
◆Fujito, T. (2012)
How to Trim a MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover, ACM Trans. Algorithms, 8(2) 16:1-16:11

キーワード

多項式時間アルゴリズム,近似アルゴリズム,マトロイド,動的計画法,分割統治法,計算量,NP-困難性,数理計画,双対性

テーマ2:実用モデルに対する応用アルゴリズムの開発

概要

テーマ1でのアルゴリズムの研究は,アルゴリズムの設計手法の一般化,既存のアルゴリズムで解ける問題のクラスの拡大を目指したものであるが,このテーマでは特殊な構造を持った現実の問題を解くアルゴリズムの開発・実装を行います.現実の要求に基づく問題を扱うことを目指しますが,現実の細かな要求条件を完全に数学モデルで記述すると見通しが悪くなるので,問題の特性を失わない範囲で簡略化したモデルを対象とします.種々のアルゴリズムを組合せ,データ構造による高速化などにより,問題の構造を利用した効率のよいアルゴリズムを実現します.提案するアルゴリズムの性能の評価についても理論的解析だけでなく,実データやベンチマークに対する計算機実験による評価も取り入れます.現場の要求からさらに特殊なモデル化が必要な場合にはこれに応じて特化したアルゴリズムの開発も行っていきます.

キーワード

グラフ,ネットワーク,スケジューリング問題,データ構造,アルゴリズムの実装,オペレーションズ・リサーチ

担当授業科目名(科目コード)

アルゴリズムとデータ構造 (B1361003a)
計算理論 (B13630100)
アルゴリズム工学特論 (M23621040)

その他(受賞、学会役員等)

受賞等
平成19年度山下記念研究賞(情報処理学会)


ページの先頭へ戻る