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

Adi Rosen; Amos Korman; Pierre Fraigniaud; Yuval Emek

arxiv: 0902.1378 · v1 · submitted 2009-02-09 · 💻 cs.DS

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

Yuval Emek , Pierre Fraigniaud , Amos Korman , Adi Rosen This is my paper

classification 💻 cs.DS

keywords algorithmfunctionworkcompetitivek-serverstrictlyadditivec-competitive

0 comments

read the original abstract

We 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.

This paper has not been read by Pith yet.

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

discussion (0)