3点上のオンラインページ移動問題に対する新しい上下界

概要

論文の詳細を見る
ページ移動問題とは,辺重みw:E→R^+を持つグラフG=(V,E),正整数D,点列s_0,r_1,…,r_k∈Vが与えられ,Σ^k_<i=1>(d_s_<i-1>r_i+D・d_s_<i-1>s_i)を最小化するような点列s_1,…,s_k∈Vを求める問題である.ただし,d_<uv>はuとv結ぶパスの辺の重みの最小和である.本報告ではこの問題に対する決定的なオンラインアルゴリズムについて考える.すべてのグラフとDに対して3より小さい競合比を持つブルゴリズムは存在しないことが知られている.また,3点上でD=1の場合に対する3-競合アルゴリズムが知られている.しかし,3点上でD≥2の場合に対する3-競合オンラインアルゴリズムが存在するか否かは,著者が知る限り知られていない.本稿では,3点上でD=2の場合には3-競合アルゴリズムが存在するが,D≥3の場合には3-競合アルゴリズムは存在しないことを示す.また任意のDに対する3.1467-競合オンラインアルゴリズムを示す.
2008-10-31