東北大学大学院情報科学研究科 -- Graduate School of Information Sciences,Tohoku University --

伊藤　健洋助教が情報処理学会東北支部の第二回野口研究奨励賞を受賞

■受賞の感想　この度は，野口研究奨励賞をいただくことができ，たいへん光栄です．これも西関教授，周准教授をはじめとする先生方のご指導のおかげです．東北大学に学部生として入学してから約10年になりますが，研究者としての私を基礎から育てていただきました．この賞を励みに，今後も研究に取り組んで参ります．これからもご指導，ご鞭撻の程よろしくお願いいたします．
		伊藤　健洋　助教
■研究の概要　現在，様々な問題が“グラフ”を用いてモデル化されている．グラフとは，いくつかの点と，それらの点同士を結ぶ何本かの辺からなるもので，いろいろな構造を抽象的に表現することに優れている．例えば，図(a)はコンピュータネットワークの構造をグラフで表現した例であり，各点は丸もしくは四角で描かれ，各辺は直線分で描かれている．ここで，丸の点は端末を表し，四角の点はサーバを表し，各辺はネットワーク（ケーブル）を表している．　本研究では，ビデオ・オン・デマンド用ファイル転送問題や電力系統の配電融通問題などに応用がある「需要点と供給点があるグラフの分割問題」を扱った．グラフの各点には“需要点”または“供給点”の役割が与えられ，それぞれに“需要量”または“供給量”と呼ばれる正の実数が与えられている．このとき，できるだけ多くの需要を満足したい．即ち，供給を受けている需要点の需要量の合計を最大にするようなグラフの分割を見つけたい．例えば，図(a)のグラフに対し，図(b)はグラフ分割の一例を示している．ここで，各供給点は四角で描かれ，各需要点は丸で描かれている．また，図(b)において，供給を受けている需要点は，その供給元の供給点と同じ色で塗られている．このような分割を見つける問題は，ビデオ・オン・デマンドにおいてサーバの割当方法を見つける問題や，電力系統において停電の復旧方法を見つける問題などに応用できる．　この分割問題は，たとえグラフが“木”と呼ばれる単純な構造をしていても，いわゆるNP困難な問題である．したがって，木に対してさえ最適解を高速に求めることは絶望的である．そこで本研究では，木に対して最適解に極めて近い近似解を高速に求めることができる近似アルゴリズムを与えた．このアルゴリズムは完全近似スキーム（FPTAS）と呼ばれるものになっており，いわば最良の近似アルゴリズムである．


■論文等 [対象論文] Takehiro Ito, Xiao Zhou and Takao Nishizeki, “Partitioning Trees of Supply and Demand”　　　 International Journal of Foundations of Computer Science, Vol. 16, No. 4, pp. 803-827, 2005. [参考論文1] Takehiro Ito, Xiao Zhou and Takao Nishizeki, “Partitioning Graphs of Supply and Demand” Discrete Applied Mathematics, to appear. [参考論文2] Takehiro Ito, Erik D. Demaine, Xiao Zhou and Takao Nishizeki, “Approximability of Partitioning Graphs with Supply and Demand” Proc. of 17th Annual International Symposium on Algorithms and Computation (ISAAC2006), Lecture Notes in Computer Science Vol. 4288, pp. 121-130, 2006.

伊藤 健洋 助教が 情報処理学会東北支部の第二回野口研究奨励賞を受賞

伊藤　健洋助教が
情報処理学会東北支部の第二回野口研究奨励賞を受賞