On the additive constant of the k-server Work Function Algorithm

We consider the Work Function Algorithm for the k-server problem (Chrobak and Larmore, 1991; Koutsoupias and Papadimitriou, 1995) [2] and [4]. We show that if the Work Function Algorithm is c-competitive, then it is also strictly  (2c)(2c)-competitive. As a consequence of (Koutsoupias and Papadimitriou, 1995) [4] this also shows that the Work Function Algorithm is strictly (4k−2)(4k−2)-competitive.

Research highlights
► If the Work Function Algorithm for the k-server problem is c  -competitive, then it is also strictly (2c)(2c)-competitive.