## 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