正多角形領域に対するオンライン追跡問題

スポンサーリンク

概要

論文の詳細を見る
我々は動かすべきサーバが1個しかないサーバ配置問題を考察する。もしサーバが要求点そのものに移動しなければならないのであれば選択の余地がないので問題として成立レない。しかし、サーバの移動を要求点そのものでなく、その「近く」でも良いとするなら話は違ってくる。つまり要求に対して一定の領域を対応させ、サーバはその領域内のいずれかに移動させれば良いとする(オンライン追跡問題)。本稿では領域が正n角形の場合に注目する。まず貪欲アルゴリズムの解析を行い、競合比がO(n)であることを示す。次に幾つかの入力例に対する仕事関数アルゴリズムの性能評価を行い、適切な設定の下で定数競合比を達成すると予想する。
一般社団法人情報処理学会の論文
2007-09-21

著者

関連論文

もっと見る

スポンサーリンク