米山純央さん（理工学研究科 博士課程前期課程 2年 情報科学専攻 巳波弘佳研究室）が12月21日（木）、22日（金）にサテライトキャンパスひろしまで開催された電子情報通信学会インターネットアーキテクチャ研究会において「学生研究奨励賞」を受賞しました。

発表概要は以下のとおりです。

【タイトル】
リンク数が限定された光パス収容設計問題に対する多項式時間近似スキーム
【著者】
米山純央、巳波弘佳
【概要】
高速で大容量通信を可能とする光伝送ネットワークは、現在の情報ネットワークを支える重要なインフラである。光伝送ネットワークでは、波長が割り当てられている光パス上でデータが送受信される。同一リンク内では同一波長の光パスは収容できず、また利用可能な波長数（異なる波長の数）には限りがあるため、これらの制約を満たすように光パスに適切に波長を割り当てなければならない。つまり、制約を満たしつつ、できるだけ多くの光パスを収容できるような波長割当（光パス収容設計）が必要である。この設計問題は離散最適化問題として定式化されるが、一般にNP困難である。そのため、様々なヒューリスティックアルゴリズムが提案されている。本稿では、2リンクだけからなるシンプルなネットワークにおいては、任意のε近似解を多項式時間の計算量で出力できる多項式時間近似スキームが存在することを示す。これは、一般的なネットワークではNP困難であるために最適解を多項式時間で求めることは期待できないが、このようなシンプルなネットワークにおいては、最適解に近い光パス収容設計が可能であることを意味する。