Memory versus randomization in on-line algorithms

P. Raghavan, M. Snir

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)683-707
Number of pages25
JournalIBM Journal of Research and Development
Volume38
Issue number6
DOIs
StatePublished - 1994
Externally publishedYes

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'Memory versus randomization in on-line algorithms'. Together they form a unique fingerprint.

Cite this