## DIMACS TR: 99-59

## Note on the Work Function Algorithm

### Author: Bela Csaba

**
ABSTRACT
**

We prove that the work function algorithm is $(n-1)$-competitive
for the $k$-server problem, where $n$ is the number of points
in the metric space. This gives improved upper bounds when $k+3
\leq n \leq 2k-1$; in particular, it shows that the work function
algorithm is optimal for $k=n-1$.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-59.ps.gz

DIMACS Home Page