TY - GEN A1 - Hiller, Benjamin A1 - Vredeveld, Tjark T1 - On the optimality of Least Recently Used N2 - 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. T3 - ZIB-Report - 08-39 KW - Paging KW - locality of reference KW - LRU KW - Onlinealgorithmen KW - Stochastische Dominanz KW - paging KW - locality of reference KW - LRU KW - online algorithms KW - stochastic dominance Y1 - 2008 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1092 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-10928 SN - 1438-0064 ER -