The harmonic k-server algorithm is competitive
01 January 2000
The k-server problem isa generalization of the paging problem, and is the most studied problem in the area of competitive online problems. The Harmonic algorithm is a very natural and simple randomized algorithm for the k-server problem. We give a simple proof that the Harmonic k-server algorithm is competitive. The competitive ratio we prove is the best currently known for the algorithm. The Harmonic algorithm is memoryless and time-efficient; This is the only such algorithm known to be competitive for the k-server problem.