On May 2, 2018, Prof. Dr. Marcin Bienkowski will give a talk about "On phase-based algorithms for online file migration" in the context of the SFB 901.
Abstract:
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, Charikar and Indyk (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 no fixed-length phase-based algorithm can beat the competitive ratio of 4.086.
Joint work with Jarek Byrka and Marcin Mucha, published at ICALP 2017.