Settling the Randomized k-sever Conjecture on Some Special Metrics

الأصل · EN

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(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(k n)-competitive randomized k-sever algorithm.