3点上の最適なオンラインページ移動
スポンサーリンク
概要
- 論文の詳細を見る
ページ移動問題とは,辺重みを持つ無向グラフ G=(V,E),正整数 D,点列 s0,r1,...,rk∈V が与えられ,Σki=1(dsi-1ri+D・dsi-1si) を最小化するような点列 s1,...,sk∈V を求める問題である.ただし,d(u,v) は点 u と点 v の G 上の距離である.この問題は長年研究されているが,|V|=3 という極端に単純な場合ですら,D=1,2 の場合を除き,決定的オンラインアルゴリズムの厳密な競合比は知られていない.本報告では 3 点上のページ移動問題に対する決定的なオンラインアルゴリズムの競合比が一般の D に対して 3+Θ(1/D) であることを示す.
- 2011-11-11
著者
関連論文
- リングにおける競合的オンラインデータ移動アルゴリズム
- 分割子に基づく高次元格子への小さい辺負荷を持つグラフ埋め込み(グラフ,ペトリネット,ニューラルネット,及び一般)
- 分割子に基づく高次元格子への小さい辺負荷を持つグラフ埋め込み(グラフ,ペトリネット,ニューラルネット,及び一般)
- グラフの幅2の真のパス分解を求める効率的アルゴリズム
- グラフの格子への辺負荷最小埋め込みの計算複雑度について
- グラフのハイパーキューブへの辺負荷最小の埋め込み
- 3点上の最適なオンラインページ移動
- 2-パス光ネットワークにおける最適波長割り当て
- キャタピラネットワークにおけるパス彩色
- リングネットワークにおけるファイル配置問題について
- グラフを梯子へ最小辺負荷で埋め込む多項式時間アルゴリズム
- 3点上のオンラインページ移動問題に対する新しい上下界
- リングネットワークにおけるページ移動について
- 一様ネットワークにおける厳密競合オンラインデータ管理
- 効率的に分割できるグラフの同点数格子への小さい辺負荷を持つ埋め込み
- 定数コストの横断辺を持つ梯子状ネットワークの最適化
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト(グラフ,ペトリネット,ニューラルネット,及び一般)
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト(グラフ,ペトリネット,ニューラルネット,及び一般)
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト