[Updated on Apr. 18] Integration of CiNii Articles into CiNii Research


Bibliographic Information

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

Search this article



ファイル配置問題とは,与えられたネットワーク,データ集合,読み書き要求系列に対し,要求の実現とデータの再配置に必要な通信コストの総和が最小となるように,データを動的に再配置する問題である.本稿では,リングネットワークにおけるファイル配置問題を考える.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.



See more


Report a problem

Back to top