Y. Bartal and E. Koutsoupias.
On the competitive ratio of the work function algorithm for the
k-server problem.
In Theoretical Computer Science, 324(2-3):337--345,
September 2004.
Abstract
The $k$-server problem is one of the most fundamental online problems. The problem is to schedule $k$ mobile servers to visit a sequence of points in a metric space with minimum total mileage. The $k$-server conjecture of Manasse, McGeogh, and Sleator states that there exists a $k$-competitive online algorithm. The conjecture has been open for over 15 years. The top candidate online algorithm for settling this conjecture is the Work Function Algorithm (WFA) which was shown to have competitive ratio at most $2k-1$. In this paper we lend support to the conjecture that WFA is in fact $k$-competitive by proving that it achieves this ratio in several special metric spaces: the line, the star, and all metric spaces with $k+2$ points.Bib
@Article{BK04,
author = {Y. Bartal and E. Koutsoupias},
title = {On the Competitive Ratio of the Work Function Algorithm
for the $k$-Server Problem},
journal = {Theoretical Computer Science},
year = {2004},
volume = {324},
number = {2-3},
pages = {337--345},
month = 20 # sep,
note = {An early version appeared in STACS 2000},
}
@string{STACS00 = {17th Annual Symposium on Theoretical Aspects of
Computer Science}}
@InProceedings{BK00,
author = {Y. Bartal and E. Koutsoupias},
title = {On the Competitive Ratio of the Work Function Algorithm
for the $k$-Server Problem},
booktitle = STACS00,
year = 2000,
month = {17--19 } # feb,
address = {Lille, France},
pages = {605--613},
}