| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429072 | Information Processing Letters | 2010 | 4 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yuval Emek, Pierre Fraigniaud, Amos Korman, Adi Rosén,