Concepedia

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

Don Coppersmith, Peter G. Doyle, Prabhakar Raghavan, Marc Snir

1990 · 57 citations · 22 references

DOIFull text

Open access

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.

References

22

Inequalities: Theory of Majorization and its Applications.

Barry C. Arnold, Albert W. Marshall, Ingram Olkin · Journal of the American Statistical Association · 1981 · 5K citations

, , +13

Amortized efficiency of list update and paging rules

Daniel D. Sleator, Robert E. Tarjan · Communications of the ACM · 1985 · 2.1K citations · Full text

, , +16

An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology

Leonard E. Baum, J. A. Eagon · Bulletin of the American Mathematical Society · 1967 · 1K citations · Full text

, , +9

Competitive snoopy caching

Anna R. Karlin, Mark S. Manasse, Larry Rudolph et al. · Algorithmica · 1988 · 603 citations

, , +6

Competitive paging algorithms

Amos Fiat, Richard M. Karp, Michael Luby et al. · Journal of Algorithms · 1991 · 455 citations · Full text

, , +6