Journal
ACM TRANSACTIONS ON ALGORITHMS
Volume 15, Issue 4, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3340296
Keywords
File migration; factor-revealing linear programs; online algorithms; competitive analysis
Funding
- Polish National Science Centre [2016/22/E/ST6/00499, 2015/18/E/ST6/00456]
- European Research Council (ERC) under the European Union [677651]
Ask authors/readers for more resources
We construct a deterministic 4-competitive algorithm for the online file migration problem, beating the currently best 20-year-old, 4.086-competitive MovE-To-LOCAL-MIN (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 linear program) 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, then the competitive ratio is at least 4.086.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
