Dynamic Beats Fixed
Marcin Bieńkowski, Jarosław Byrka, Marcin Mucha · ACM Transactions on Algorithms · 2019
We construct a deterministic 4-competitive algorithm for the online file migration problem, beating the currently best 20-year-old, 4.086-competitive M ove -T o -L ocal -M in (M tlm ) algorithm by Bartal et al. (SODA 1997). Like M tlm , 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.