Randomized Online File Allocation on Uniform Cactus Graphs

スポンサーリンク

概要

• 論文の詳細を見る

• 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

著者

• MATSUBAYASHI Akira

  Division of Electrical Engineering and Computer Science, Kanazawa University

• Matsubayashi Akira

  Division Of Electrical Engineering And Computer Science Kanazawa University

• Matsubayashi Akira

  Division Of Electrical Engineering And Computer Science Graduate School Of Natural Science And Techn

• Kawamura Yasuyuki

  Division Of Electrical Engineering And Computer Science Kanazawa University

関連論文

• Minimum energy broadcast on rectangular grid wireless networks (コンピュテーション)
• AS-1-5 Separator-Based Graph Embedding into Higher Dimensional Grids with Small Edge-Congestion
• Path coloring on binary caterpillars
• Randomized Online File Allocation on Uniform Cactus Graphs

スポンサーリンク