Randomized k-server on hierarchical binary trees
Aaron S. Cote, Adam Meyerson, Laura Poplawski · 2008
We design a randomized online algorithm for k-server on binary trees with hierarchical edge lengths, with expected competitive ratio O(log Delta), where Delta is the diameter of the metric. This is one of the first k-server algorithms with competitive ratio poly-logarithmic in the natural problem parameters, and represents substantial progress on the randomized k-server conjecture. Extending the algorithm to trees of higher degree would give a competitive ratio of O(log2 Delta log n) for the k-server problem on general metrics with n points and diameter Delta.