Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis

Joan Boyar, Sushmita Gupta, Kim Skak Larsen

Publikation: Bidrag til tidsskriftKonferenceartikelForskningpeer review

Abstrakt

Access graphs, which have been used previously in connection with competitive analysis to model locality of reference in paging, are considered in connection with relative worst order analysis. In this model, FWF is shown to be strictly worse than both LRU and FIFO on any access graph. LRU is shown to be strictly better than FIFO on paths and cycles, but they are incomparable on some families of graphs which grow with the length of the sequences.
OriginalsprogEngelsk
BogserieLecture Notes in Computer Science
Vol/bind7357
Sider (fra-til)328-339
Antal sider12
ISSN0302-9743
DOI
StatusUdgivet - 2012
Begivenhed13th Scandinavian Symposium and Workshops on Algorithm Theory - Helsinki, Finland
Varighed: 4. jul. 20126. jul. 2012
Konferencens nummer: 13

Konference

Konference13th Scandinavian Symposium and Workshops on Algorithm Theory
Nummer13
Land/OmrådeFinland
ByHelsinki
Periode04/07/201206/07/2012

Emneord

  • online algorithms
  • paging
  • access graphs
  • relative worst order analysis

Fingeraftryk

Dyk ned i forskningsemnerne om 'Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis'. Sammen danner de et unikt fingeraftryk.

Citationsformater