リングネットワークにおけるファイル配置問題について

機関リポジトリ Web Site 参考文献4件

書誌事項

タイトル別名
  • リング ネットワーク ニ オケル ファイル ハイチ モンダイ ニ ツイテ
  • On File Allocation on Uniform Ring Networks

この論文をさがす

抄録

金沢大学理工研究域電子情報学系

ファイル配置問題とは,与えられたネットワーク,データ集合,読み書き要求系列に対し,要求の実現とデータの再配置に必要な通信コストの総和が最小となるように,データを動的に再配置する問題である.本稿では,リングネットワークにおけるファイル配置問題を考える.Bartal,Fiat,Rabaniはあるネットワークでc-競合オンラインシュタイナー木アルゴリズムが存在するとき,そのネットワークにおいて適応オンラインアドバーサリに対する(2+√<3>)c-競合となる確率的アルゴリズムを示した.リングネットワークにおいて2-競合オンラインシュタイナー木アルゴリズムが存在することから,このアルゴリズムはリングネットワークにおいて4+2√<3>(≃7.464)-競合のファイル配置アルゴリズムである.本稿では重みなしリングネットワークにおいて適応オンラインアドバーサリに対する7-競合確率的アルゴリズムを示すとともに,決定的アルゴリズムの競合比の下界4.25を示す. Given a network, a set of data objects, and a sequence of requests, the file allocation problem is to compute dynamic allocation of the data objects on the network so that the total communication cost of services for the requests and allocation of data object is minimized. In this paper we consider the file allocation problem on ring networks. Bartal, Fiat, and Rabani showed that if there exists a c-competitive online Steiner tree algorithm on a network, then there exists a (2+√<3>)c-competitive randomized file allocation algorithm against adaptive-online adversary on the network. Their result implies a 4+2√<3>(≃7,464)-competitive file allocation algorithm against adaptive-online adversary on ring networks since a greedy Steiner tree algorithm is 2-competitive on ring networks. In this paper we show a 7-competitive randomized algorithm against adaptive-online adversary and give a lower bound of 4.25 of deterministic algorithm on uniform ring networks.

収録刊行物

参考文献 (4)*注記

もっと見る

詳細情報 詳細情報について

問題の指摘

ページトップへ