Publication
STOC 1990
Conference paper
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.