MEMORY VERSUS RANDOMIZATION IN ONLINE ALGORITHMS

On-line algorithms service sequences of requests, one at a time, witho ut knowing future requests. We compare their performance with the perf ormance of algorithms that generate the sequences and service them as well. In many settings, on-line algorithms perform almost as well as o ptimal off-line algorithms, by using statistics about previous request s in the sequences. Since remembering such information may be expensiv e, we consider the use of randomization to eliminate memory. In the pr ocess, we devise and study performance measures for randomized on-line algorithms. We develop and analyze memoryless randomized on-line algo rithms for the cacheing problem and its generalizations.