Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

CRC 901 – On-The-Fly Computing (OTF Computing) Show image information

CRC 901 – On-The-Fly Computing (OTF Computing)

Wednesday, 02.05.2018 | 14.00 - 15.00 Uhr | Fürstenallee 11, Raum F1.544

Talk given by Prof. Dr. Marcin Bienkowski (University of Wroclaw)

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.


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.

The University for the Information Society