On the Additive Constant of the k-server Work Function Algorithm

Simple item page
dc.creatorEmek, Yuval
dc.creatorFraigniaud, Pierre
dc.creatorKorman, Amos
dc.creatorRosen, Adi
dc.date2009-02-09
dc.date.accessioned2026-07-07T12:39:24Z
dc.date.available2026-07-07T12:39:24Z
dc.descriptionWe consider the Work Function Algorithm for the k-server problem. We show that if the Work Function Algorithm is c-competitive, then it is also strictly (2c)-competitive. As a consequence of [Koutsoupias and Papadimitriou, JACM 1995] this also shows that the Work Function Algorithm is strictly (4k-2)-competitive.
dc.description7 pages
dc.identifierhttps://arxiv.org/abs/0902.1378
dc.identifierhttp://arxiv.org/abs/0902.1378
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/219100
dc.subjectData Structures and Algorithms
dc.titleOn the Additive Constant of the k-server Work Function Algorithm
dc.typetext

Files

Collections

arXiv