Sachin Lodha - Kservers (abstract)

Abstract

We give a $O(n^{2 \over 3}\log{n})$-competitive randomized $k$--server algorithm when the underlying metric space is given by $n$ equally spaced points on a line. For $n = k + o(k^{3 \over 2}/\log{k})$, this algorithm is $o(k)$--competitive.