Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

Dynamic beats fixed : on phase-based algorithms for file migration

Uproszczony widok
dc.abstract.enIn 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryPolska
dc.conference.datefinish2017-07-14
dc.conference.datestart2017-07-10
dc.conference.placeWarszawa
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesshortcutICALP
dc.conference.shortcutICALP 2017
dc.contributor.authorBieńkowski, Marcin
dc.contributor.authorByrka, Jarosław
dc.contributor.authorMucha, Marcin
dc.date.accessioned2024-01-24T22:15:25Z
dc.date.available2024-01-24T22:15:25Z
dc.date.issued2017
dc.description.accesstimeAT_PUBLICATION
dc.description.financeNie dotyczy
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.ICALP.2017.13
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/105483
dc.identifier.weblinkhttps://doi.org/10.4230/LIPIcs.ICALP.2017.13
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages13:1-13:14
dc.rightsCC-BY
dc.sciencecloudnosend
dc.subject.enfile migration
dc.subject.enfactor-revealing linear programs
dc.subject.enonline algorithms
dc.subject.encompetitive analysis
dc.titleDynamic beats fixed : on phase-based algorithms for file migration
dc.typeJournalArticle
dspace.entity.typePublication