Refine
Year of publication
- 2008 (3) (remove)
Document Type
- ZIB-Report (2)
- In Proceedings (1)
Language
- English (3)
Is part of the Bibliography
- no (3)
Keywords
- Stochastische Dominanz (2)
- online algorithms (2)
- stochastic dominance (2)
- LRU (1)
- Markov chains (1)
- Markov-Ketten (1)
- Online-Algorithmen (1)
- Onlinealgorithmen (1)
- Paging (1)
- Probabilistische Analyse (1)
- locality of reference (1)
- paging (1)
- probabilistic analysis (1)
Institute
It is well known that competitive analysis yields too pessimistic results when applied to the paging problem and it also cannot make a distinction between many paging strategies. Many deterministic paging algorithms achieve the same competitive ratio, ranging from inefficient strategies as flush-when-full to the good performing least-recently-used (LRU). In this paper, we study this fundamental online problem from the viewpoint of stochastic dominance. We show that when sequences are drawn from distributions modelling locality of reference, LRU is stochastically better than any other online paging algorithm.
This paper proposes a new method for probabilistic analysis of online algorithms that is based on the notion of stochastic dominance. We develop the method for the Online Bin Coloring problem introduced by Krumke et al. Using methods for the stochastic comparison of Markov chains we establish the strong result that the performance of the online algorithm GreedyFit is stochastically dominated by the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic picture than competitive analysis and explains the behavior observed in simulations.