Random Walks on Weighted Graphs, and Applications to On-line Algorithms.

We show that the amortized analysis of on-line algorithms is tied to the study of random walks on graphs and hence to the theory of electric networks. In the past, electric networks have been used to analyze random walks. Here we use electric networks to synthesize optimal random walks. We use these optimal random walks to construct probably good, memoryless on-line algorithms for the server problem of Manasse, McGeoch, and Sleator, and for the metrical task systems of Borodin, Linial, and Saks. These on-line algorithms are extremely simple, and cover almost all previously known results for these two problems.