RANDOM-WALKS ON WEIGHTED GRAPHS AND APPLICATIONS TO ONLINE ALGORITHMS

Authors
COPPERSMITH D DOYLE P RAGHAVAN P SNIR M
Citation
D. Coppersmith et al., RANDOM-WALKS ON WEIGHTED GRAPHS AND APPLICATIONS TO ONLINE ALGORITHMS, Journal of the Association for Computing Machinery, 40(3), 1993, pp. 421-453
Citations number
23
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics
Journal title
Journal of the Association for Computing Machinery
ISSN journal
00045411 → ACNP
Volume
40
Issue
3
Year of publication
1993
Pages
421 - 453
Database
ISI
SICI code
Abstract
The design and analysis of randomized on-line algorithms are studied. This problem is shown to be closely related to the synthesis of random walks on graphs with positive real costs on their edges. A theory is developed for the synthesis of such walks, and it is employed to desig n competitive on-line algorithms.