理工学部

情報工学科

インターネットに代表される情報ネットワークやVLSIの物理設計等で生じる自然な問題は，その接続構造に基づいてグラフ表現され解析されることが多い。このように構造をもつネットワーク上での様々な問題はNP-困難であることが多く，ごく普通に起こるサイズの問題でも，コンピュータが将来どれほど高速化されても実用時間の範囲では解けないといわれている。そこで近似解を求めて利用することになるが，その際重要になるのが解の品質である。厳密解に匹敵する高品質な解を求める研究が近似アルゴリズムの研究である。本研究では，高品質の解を保証する近似アルゴリズムの研究を行っている。より具体的には，

（a）　施設配置問題
（b）　配送計画問題
（c）　スケジューリング
（d）　高信頼ネットワーク設計
（e）　混雑を考慮したインターネットフロー制御
（f）　インターネットルーティングアルゴリズム
などの研究を行っている。