99-59: Note on the Work Function Algorithm

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