For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Randomized Online File Allocation on Uniform Cactus Graphs
Yasuyuki KAWAMURA Akira MATSUBAYASHI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2009/12/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm Theory
online algorithm, file allocation, data management, cactus graph,
Full Text: PDF>>
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.