Randomized Online File Allocation on Uniform Cactus Graphs

Yasuyuki KAWAMURA  Akira MATSUBAYASHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.12   pp.2416-2421
Publication Date: 2009/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.2416
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm Theory
Keyword: 
online algorithm,  file allocation,  data management,  cactus graph,  

Full Text: PDF>>
Buy this Article




Summary: 
We study the online file allocation problem on ring networks. In this paper, we present a 7-competitive randomized algorithm against an adaptive online adversary on uniform cactus graphs. The algorithm is deterministic if the file size is 1. Moreover, we obtain lower bounds of 4.25 and 3.833 for a deterministic algorithm and a randomized algorithm against an adaptive online adversary, respectively, on ring networks.