@article{oai:kanazawa-u.repo.nii.ac.jp:00009788,
 author = {川村, 泰之 and 小林, 正雄 and 松林, 昭},
 issue = {119},
 journal = {情報処理学会研究報告. AL, アルゴリズム研究会報告},
 month = {Nov},
 note = {ファイル配置問題とは,与えられたネットワーク,データ集合,読み書き要求系列に対し,要求の実現とデータの再配置に必要な通信コストの総和が最小となるように,データを動的に再配置する問題である.本稿では,リングネットワークにおけるファイル配置問題を考える.Bartal,Fiat,Rabaniはあるネットワークでc-競合オンラインシュタイナー木アルゴリズムが存在するとき,そのネットワークにおいて適応オンラインアドバーサリに対する(2+√<3>)c-競合となる確率的アルゴリズムを示した.リングネットワークにおいて2-競合オンラインシュタイナー木アルゴリズムが存在することから,このアルゴリズムはリングネットワークにおいて4+2√<3>(&sime;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>(&sime;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., 金沢大学理工研究域電子情報学系},
 pages = {41--47},
 title = {リングネットワークにおけるファイル配置問題について},
 volume = {2007},
 year = {2007}
}