The harmonic online K-server algorithm is competitive
- 1 January 1991
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 260-266
- https://doi.org/10.1145/103418.103448
Abstract
We show that the Harmonic algorithm for the online K-server problem is ( ~11 x 2K – 2K)competitive against an adaptive online adversary for K 22. From a result of [BBKTW90], we get a deterministic algorithm which is ( ~K x 2K – 2102competitive. These are the best competitive ratios that have been published so far for online algorithms over a general metric space when K >2.Keywords
This publication has 0 references indexed in Scilit: