A simple analysis of the harmonic algorithm for two servers
HARMONIC is a randomized k-server algorithm that chooses the servers with probabilities proportional to the inverses of distances to the request paint. We present a simple proof that HARMONIC is 3-competitive for k = 2. (C) 2000 Elsevier Science B.V. All rights reserved.
randomization analysis of algorithms theory of computation online algorithms