情報処理学会 第81回全国大会講演要旨

本研究では，通信ネットワークをグラフにモデル化し，ある1点のユーザに対して，複数サーバからサービスを提供する状況を考える．ただし，このサービス提供の途中でも，他のユーザからの要求に応えられるように「余力」を多く残せるようなサーバ割当を行いたい．本稿では特に，各サーバからユーザへの通信経路が事前に指定されているとする．このような問題は，一般に強NP困難であることが知られている．そこで本稿では，この問題に対してパラメータ複雑性の観点から解析を行った．パラメータとして，サーバ数・ユーザ数・要求量及びそれらの組合せを扱い，容易性・困難性両方の結果を与えた．