Random walks on weighted graphs and applications to on-line algorithms
| Author(s) : | Marc Snir Prabhakar Raghavan Peter Doyle, |
| Publisher : | N/A |
| Publication Date : | 1990 |
| ISSN : | N/A |
| 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. 1, |