Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

On the optimality of Least Recently Used

Please always quote using this URN: urn:nbn:de:0297-zib-10928
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Benjamin HillerORCiD, Tjark Vredeveld
Document Type:ZIB-Report
Tag:LRU; Onlinealgorithmen; Paging; Stochastische Dominanz; locality of reference
LRU; locality of reference; online algorithms; paging; stochastic dominance
Date of first Publication:2008/09/25
Series (Serial Number):ZIB-Report (08-39)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.