野口研究奨励賞受賞

伊藤健洋（いとう　たけひろ） 東北大学大学院情報科学研究科

研究の概要:
　現在，様々な問題が“グラフ”を用いてモデル化されている．グラフとは，い
　くつかの点と，それらの点同士を結ぶ何本かの辺からなるもので，いろいろな
構造を抽象的に表現することに優れている．例えば，図(a)はコンピュータネット
ワークの構造をグラフで表現した例であり，各点は丸もしくは四角で描かれ，各
辺は直線分で描かれている．ここで，丸の点は端末を表し，四角の点はサーバを
表し，各辺はネットワーク（ケーブル）を表している．
　本研究では，ビデオ・オン・デマンド用ファイル転送問題や電力系統の配電融
通問題などに応用がある「需要点と供給点があるグラフの分割問題」を扱った．グ
ラフの各点には“需要点”または“供給点”の役割が与えられ，それぞれに“需要
量”または“供給量”と呼ばれる正の実数が与えられている．このとき，できるだ
け多くの需要を満足したい．即ち，供給を受けている需要点の需要量の合計を最大
にするようなグラフの分割を見つけたい．例えば，図(a)のグラフに対し，図(b)は
グラフ分割の一例を示している．ここで，各供給点は四角で描かれ，各需要点は丸
で描かれている．また，図(b)において，供給を受けている需要点は，その供給元
の供給点と同じ色で塗られている．このような分割を見つける問題は，ビデオ・オ
ン・デマンドにおいてサーバの割当方法を見つける問題や，電力系統において停電
の復旧方法を見つける問題などに応用できる．
　この分割問題は，たとえグラフが“木”と呼ばれる単純な構造をしていても，い
わゆるNP困難な問題である．したがって，木に対してさえ最適解を高速に求めるこ
とは絶望的である．そこで本研究では，木に対して最適解に極めて近い近似解を高
速に求めることができる近似アルゴリズムを与えた．このアルゴリズムは完全近似
スキーム（FPTAS）と呼ばれるものになっており，いわば最良の近似アルゴリズム
である．



受賞の感想：
　この度は，野口研究奨励賞をいただくことができ，たいへん光栄です．これも西
関教授，周准教授をはじめとする先生方のご指導のおかげです．東北大学に学部生
として入学してから約10年になりますが，この東北の地で研究者としての私を基礎
から育てていただきました．この賞を励みに，今後も研究に取り組んで参ります．
これからもご指導，ご鞭撻の程よろしくお願いいたします．


受賞の様子：
　




[対象論文] Partitioning Trees of Supply and Demand. 
Takehiro Ito, Xiao Zhou and Takeo Nishizeki.
International Journal of Foundations of Computer Science, Vol.16, No.4, pp.803-827. 2005

[参考論文1] Partitioning Graphs of Supply and Demand. 
Takehiro Ito, Xiao Zhou and Takeo Nishizeki.
Discrete Applied Mathematics, to appear

[参考論文2] Approximability of Partitioning Graphs with Supply and Demand. 
Takehiro Ito, Erik D. Demaine, Xiao Zhou and Takeo Nishizeki.
Journal of Discrete Algorithms, submitted