ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Alles auswählen Exportieren

Unbekannt

On the optimality of Least Recently Used (2008)

Hiller, Benjamin ; Vredeveld, Tjark

zur Merkliste hinzufügen auf der Merkliste

Details

Publikationsdatum: 2020-08-05

Beschreibung: 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.

Schlagwort(e): ddc:510

Sprache: Englisch

Materialart: reportzib , doc-type:preprint

Format: application/pdf

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

OPUS

PDF

Überblick

Treffer 1 - 1 | 1 Treffer