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