Random walks on weighted graphs, and applications to on-line algorithms.

Abstract

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.