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$.
DIMACS Home Page