Memory versus randomization in on-line algorithms
P. Rajhavan, Marc Snir · IBM Journal of Research and Development · 1994
On-line algorithms service sequences of requests, one at a time, without knowing future requests. We compare their performance with the performance of algorithms that generate the sequences and service them as well. In many settings, on-line algorithms perform almost as well as optimal off-line algorithms, by using statistics about previous requests in the sequences. Since remembering such information may be expensive, we consider the use of randomization to eliminate memory. In the process, we devise and study performance measures for randomized on-line algorithms. We develop and analyze memoryless randomized on-line algorithms for the cacheing problem and its generalizations.
Cited by 119 works. doi:10.1147/rd.386.0683
Authors
References
- Probability theory
- A study of replacement algorithms for a virtual-storage computer
- Amortized efficiency of list update and paging rules
- Competitive snoopy caching
- Competitive paging algorithms
- Heuristics That Dynamically Organize Data Structures
- Competitive algorithms for server problems
- A strongly competitive randomized paging algorithm
- On the power of randomization in on-line algorithms
- The electrical resistance of a graph captures its commute and cover times