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

Joan Boyar, Sushmita Gupta, Kim Skak Larsen

Research output: Contribution to journalConference articleResearchpeer-review

Abstract

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.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Volume7357
Pages (from-to)328-339
Number of pages12
ISSN0302-9743
DOIs
Publication statusPublished - 2012
Event13th Scandinavian Symposium and Workshops on Algorithm Theory - Helsinki, Finland
Duration: 4. Jul 20126. Jul 2012
Conference number: 13

Conference

Conference13th Scandinavian Symposium and Workshops on Algorithm Theory
Number13
Country/TerritoryFinland
CityHelsinki
Period04/07/201206/07/2012

Fingerprint

Dive into the research topics of 'Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis'. Together they form a unique fingerprint.

Cite this