リングネットワークにおけるファイル配置問題について
スポンサーリンク
概要
- 論文の詳細を見る
ファイル配置問題とは,与えられたネットワーク,データ集合,読み書き要求系列に対し,要求の実現とデータの再配置に必要な通信コストの総和が最小となるように,データを動的に再配置する問題である.本稿では,リングネットワークにおけるファイル配置問題を考える.Bartal,Fiat,Rabaniはあるネットワークでc-競合オンラインシュタイナー木アルゴリズムが存在するとき,そのネットワークにおいて適応オンラインアドバーサリに対する(2+√<3>)c-競合となる確率的アルゴリズムを示した.リングネットワークにおいて2-競合オンラインシュタイナー木アルゴリズムが存在することから,このアルゴリズムはリングネットワークにおいて4+2√<3>(≃7.464)-競合のファイル配置アルゴリズムである.本稿では重みなしリングネットワークにおいて適応オンラインアドバーサリに対する7-競合確率的アルゴリズムを示すとともに,決定的アルゴリズムの競合比の下界4.25を示す.
- 一般社団法人情報処理学会の論文
- 2007-11-30
著者
-
松林 昭
金沢大学大学院自然科学研究科
-
松林 昭
金沢大学大学院自然科学研究科電子情報科学専攻
-
小林 正雄
金沢大学大学院自然科学研究科電子情報工学専攻
-
川村 泰之
金沢大学大学院自然科学研究科電子情報工学専攻
関連論文
- リングにおける競合的オンラインデータ移動アルゴリズム
- 分割子に基づく高次元格子への小さい辺負荷を持つグラフ埋め込み(グラフ,ペトリネット,ニューラルネット,及び一般)
- 分割子に基づく高次元格子への小さい辺負荷を持つグラフ埋め込み(グラフ,ペトリネット,ニューラルネット,及び一般)
- グラフの幅2の真のパス分解を求める効率的アルゴリズム
- グラフの格子への辺負荷最小埋め込みの計算複雑度について
- グラフのハイパーキューブへの辺負荷最小の埋め込み
- 3点上の最適なオンラインページ移動
- 2-パス光ネットワークにおける最適波長割り当て
- キャタピラネットワークにおけるパス彩色
- リングネットワークにおけるファイル配置問題について
- グラフを梯子へ最小辺負荷で埋め込む多項式時間アルゴリズム
- 3点上のオンラインページ移動問題に対する新しい上下界
- リングネットワークにおけるページ移動について
- 一様ネットワークにおける厳密競合オンラインデータ管理
- 効率的に分割できるグラフの同点数格子への小さい辺負荷を持つ埋め込み
- 定数コストの横断辺を持つ梯子状ネットワークの最適化
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト(グラフ,ペトリネット,ニューラルネット,及び一般)
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト(グラフ,ペトリネット,ニューラルネット,及び一般)
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト