Random Walks on Weighted Graphs, and Applications to On-line Algorithms (Complete Version).

We study the design and analysis of randomized on-line algorithms. We show that this problem is closely related to the synthesis of random walks on graphs with positive real costs on their edges. We develop a theory for the synthesis of such walks, and employ it to design competitive on-line algorithms. This is the complete 'journal' version of the paper. An extended abstract, circulated previously as 11218-891207-61TM, was published in the proceedings of STOC '90.