2026-03-10T16:48:18Z https://kanazawa-u.repo.nii.ac.jp/oai

oai:kanazawa-u.repo.nii.ac.jp:00008007 2024-06-20T06:39:29Z 934:935:936

Randomized Online File Allocation on Uniform Cactus Graphs Kawamura, Yasuyuki Matsubayashi, Akira Copyright (C) 2009 Institute of Electronics, Information and Communication Engineers 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 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, respetively, on ring networks. 金沢大学大学院自然科学研究科電子情報科学専攻 IEICE Institute of Electronics, Information and Communication Engineers = 電子情報通信学会 2009-12-01 2017-10-03 eng journal article VoR http://hdl.handle.net/2297/19832 https://kanazawa-u.repo.nii.ac.jp/records/8007 10.1587/transinf.E92.D.2416 AA10826272 0916-8532 IEICE Transactions on Information and Systems 92-D 12 2416 2421 https://kanazawa-u.repo.nii.ac.jp/record/8007/files/TE-PR-MATSUBAYASHI-A-2416.pdf application/pdf 187.6 kB 2017-10-03