文章基本信息

标题：Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration
本地全文：下载
作者：Marcin Bienkowski ; Jaroslaw Byrka ; Marcin Mucha 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：13:1-13:14
DOI：10.4230/LIPIcs.ICALP.2017.13
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In this paper, we construct a deterministic 4-competitive algorithm for the online file migration problem, beating the currently best 20-year old, 4.086-competitive MTLM algorithm by Bartal et al. (SODA 1997). Like MTLM, our algorithm also operates in phases, but it adapts their lengths dynamically depending on the geometry of requests seen so far. The improvement was obtained by carefully analyzing a linear model (factor-revealing LP) of a single phase of the algorithm. We also show that if an online algorithm operates in phases of fixed length and the adversary is able to modify the graph between phases, no algorithm can beat the competitive ratio of 4.086.
关键词：file migration; factor-revealing linear programs; online algorithms; competitive analysis