Template-type: ReDif-Paper 1.0
Author-Name: Hiller Benjamin 
Author-Name: Vredeveld Tjark 
Author-workplace-name: METEOR
Title: Simple optimality proofs for Least Recently Used in the presence of locality of reference
Abstract: It is well known that competitive analysis yields results that do not reflect the observed performance of online paging algorithms. Many deterministic paging algorithms achieve the same competitive ratio, ranging from inefficient strategies as flush-when-full to the well-performing least-recently-used (LRU). In this paper, we study this fundamental online problem from the viewpoint of stochastic dominance. We give simple proofs that whensequences are drawn from distributions modelling locality of reference, LRU stochastically dominates any other online paging algorithm. As a byproduct, we obtain simple proofs of some earlier results.
Keywords: operations research and management science; 
Series: Research Memoranda
Creation-Date: 2009
Number: 055
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:50c5b1ce-4764-491a-a293-4e805d1eac9b/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 431750
Handle: RePEc:unm:umamet:2009055