研究内容

近似アルゴリズムに関する研究

アルゴリズムは情報工学・情報科学の基礎を支える重要な分野である。今日、情報処理の対象は、音声や画像、さらに記号や知識処理などへとますます多様化しており、また、情報処理の形態も、シングルプロセッサでの比較的単純な処理から、複数プロセッサによる並列・協調処理や、ネットワークを介しての分散処理へと移行している。そのような新しい情報処理を指向したアルゴリズムやデータ構造について、理論面および応用面の研究を行ないたいと考えている。具体的なテーマは以下のとおりである。
高性能近似アルゴリズムの設計
グラフ問題や組合せ問題のような離散構造をもつ問題のほとんどはNP完全（最適化問題の場合はNP困難）であり、現在の計算機では計算時間が膨大になり手に負えない問題である。しかし、たとえNP困難であっても、計算機を用いて解かなければならない離散最適化問題が情報処理の現場ではますます増えている。たとえば、ORの分野では、より大規模なネットワーク上での資源割当て問題やスケジューリング問題を解かなければならない。また、人工知能の分野では推論処理のような高度な計算を要求する問題がつぎつぎと発生している。このような現実を踏まえ、たとえ求まる解が最適ではなくとも、それに十分近いことを保証できる近似アルゴリズムの設計論が今日の重要な研究テーマとなっている。
本研究では、グラフ問題を中心とした代表的離散最適化問題に対する高性能近似アルゴリズムを開発するとともに、これまでに提案されている近似アルゴリズムを設計手法の立場から調査・分類し一般的設計法の構築に向けて研究している。グラフ問題に関しては次のような成果をあげている。均等辺彩色問題の高性能アルゴリズムを開発した。重み付き独立集合問題に対する近似アルゴリズムを開発した。ネットワーク設計問題に対する組合せ的近似アルゴリズムを開発した。
近似困難性
NP困難である組合せ最適化問題に対し、最適解とアルゴリズムの出力する解（近似解）との比を保証するアルゴリズムを近似アルゴリズムといい、その比を近似比率（または近似保証）という。近似困難性の研究では、その近似比率の限界を求めることを目標とする。グラフの性質πに対しその最小辺縮約問題とは、与えられたグラフの辺を縮約してそのグラフがπを満たすようにする際の最小本数の縮約辺を求める問題であり、NP困難であることが知られている。本研究ではこの問題の近似アルゴリズムが達成する近似比率に対し下界を示した。
ハードウェアアルゴリズムの設計
距離変換は画像処理における基本的な処理であり、モルフォロジフィルタやコンピュータビジョンに応用がある。本研究ではユークリッド距離変換アルゴリズムを提案し、そのハードウェアアルゴリズムの設計とそのVLSIチップ化を行っている。また、このアルゴリズムを発展させ３次元離散ボロノイ図を効率よく求めるハードウェアアルゴリズムを提案している。
暗号計算の効率化
公開鍵暗号に用いられる楕円曲線暗号はRSA暗号とならぶ有望な方式であるが、その暗号処理で重要な演算であるスカラー倍計算に対し効率的なアルゴリズムを与えた。
最後に、アルゴリズムの研究は、計算量理論と相互に影響しあいながら発展をつづけており、今後も計算機科学の中心として内容を深めていくと思われる。そのような理論面での貢献と、応用面での研究をバランスよく行ないたいと考えている。