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

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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

Keywords

Data Structures and Algorithms

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/219100

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0902.1378
 http://arxiv.org/abs/0902.1378

Collections

arXiv