Oct. 10, 2017, 10:15 a.m.
[COG seminar] Marcin Bieńkowski: "On phase-based algorithms for file migration" (joint work with Jarosław Byrka, and Marcin Mucha)
Title: On phase-based algorithms for file migration
Authors: Marcin Bieńkowski, Jarosław Byrka, and Marcin Mucha
Speaker: Marcin Bieńkowski
Time and place: Tuesday, 10th of October, 2017, 10:15 am, room 310
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.
Joint work with Jarek Byrka and Marcin Mucha, appeared on ICALP 2017.