DIMACS TR: 2001-34

A Randomized Online Algorithm for the k-Server Problem on a Line



Authors: Bela Csaba and Sachin Lodha

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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-34.ps.gz
DIMACS Home Page