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