Settling the Randomized k-sever Conjecture on Some Special Metrics

Abstract

In this paper, we settle the randomized $k$-sever conjecture for the following metric spaces: line, circle, Hierarchically well-separated tree (HST). Specially, we show that there are $O(\log k)$-competitive randomized $k$-sever algorithms for above metric spaces. For any general metric space with $n$ points, we show that there is an $O(\log k\log n)$-competitive randomized $k$-sever algorithm.

This paper has been withdrawn by the author due to a crucial error in the LP formulation

References in corpus (1)

• Competitive Paging Algorithms