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

Joan Boyar; Sushmita Gupta; Kim Skak Larsen

doi:10.1007/978-3-642-31155-0_29

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

Joan Boyar, Sushmita Gupta, Kim Skak Larsen

Institut for Matematik og Datalogi

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer 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.

Originalsprog	Engelsk
Titel	Algorithm Theory -- SWAT 2012 : 13th Scandinavian Symposium and Workshops
Antal sider	12
Vol/bind	7357
Publikationsdato	2012
Sider	328-339
ISBN (Trykt)	978-3-642-31154-3
ISBN (Elektronisk)	978-3-642-31155-0
DOI	https://doi.org/10.1007/978-3-642-31155-0_29
Status	Udgivet - 2012
Begivenhed	13th Scandinavian Symposium and Workshops on Algorithm Theory - Helsinki, Finland Varighed: 4. jul. 2012 → 6. jul. 2012 Konferencens nummer: 13

Konference

Konference	13th Scandinavian Symposium and Workshops on Algorithm Theory
Nummer	13
Land/Område	Finland
By	Helsinki
Periode	04/07/2012 → 06/07/2012

Navn	Lecture Notes in Computer Science
ISSN	0302-9743

Emneord

online algorithms
paging
access graphs
relative worst order analysis

Dokumenter og links

10.1007/978-3-642-31155-0_29

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

1 Organisering af eller deltagelse i konference
1 Foredrag og præsentationer i privat eller offentlig virksomhed

Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
Boyar, J. (Foredragsholder)
14. dec. 2012
Aktivitet: Foredrag og mundtlige bidrag › Foredrag og præsentationer i privat eller offentlig virksomhed
13th Scandinavian Symposium and Workshops on Algorithm Theory
Boyar, J. (Deltager)
4. jul. 2012 → 6. jul. 2012
Aktivitet: Deltagelse i faglig begivenhed › Organisering af eller deltagelse i konference

Citationsformater

@inproceedings{df9ce0314b134dcba2fccfe5fc47c3b8,

title = "Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis",

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.",

keywords = "online algorithms, paging, access graphs, relative worst order analysis",

author = "Joan Boyar and Sushmita Gupta and Larsen, {Kim Skak}",

year = "2012",

doi = "10.1007/978-3-642-31155-0_29",

language = "English",

isbn = "978-3-642-31154-3",

volume = "7357",

series = "Lecture Notes in Computer Science",

publisher = "Springer Science+Business Media",

pages = "328--339",

booktitle = "Algorithm Theory -- SWAT 2012",

note = "13th Scandinavian Symposium and Workshops on Algorithm Theory ; Conference date: 04-07-2012 Through 06-07-2012",

}

Boyar, J, Gupta, S & Larsen, KS 2012, Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis. i Algorithm Theory -- SWAT 2012: 13th Scandinavian Symposium and Workshops. bind 7357, Lecture Notes in Computer Science, s. 328-339, 13th Scandinavian Symposium and Workshops on Algorithm Theory, Helsinki, Finland, 04/07/2012. https://doi.org/10.1007/978-3-642-31155-0_29

Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis. / Boyar, Joan; Gupta, Sushmita; Larsen, Kim Skak.
Algorithm Theory -- SWAT 2012: 13th Scandinavian Symposium and Workshops. Bind 7357 2012. s. 328-339 (Lecture Notes in Computer Science).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

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

AU - Boyar, Joan

AU - Gupta, Sushmita

AU - Larsen, Kim Skak

N1 - Conference code: 13

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - online algorithms

KW - paging

KW - access graphs

KW - relative worst order analysis

U2 - 10.1007/978-3-642-31155-0_29

DO - 10.1007/978-3-642-31155-0_29

M3 - Article in proceedings

SN - 978-3-642-31154-3

VL - 7357

T3 - Lecture Notes in Computer Science

SP - 328

EP - 339

BT - Algorithm Theory -- SWAT 2012

T2 - 13th Scandinavian Symposium and Workshops on Algorithm Theory

Y2 - 4 July 2012 through 6 July 2012

ER -

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

Abstract

Konference

Emneord

Dokumenter og links

SDU link

Fingeraftryk

Relaterede aktiviteter

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

13th Scandinavian Symposium and Workshops on Algorithm Theory

Citationsformater