On list update and work function algorithms

Eric J. Anderson; Kris Hildrum; Anna R. Karlin; April Rasala; Michael Saks

doi:10.1007/3-540-48481-7_26

On list update and work function algorithms

Eric J. Anderson, Kris Hildrum, Anna R. Karlin, April Rasala, Michael Saks

School of Arts and Sciences, Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has constant competitive ratio for list update. In the process, we present a new formulation of the well-known "list factoring" technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is (2 — 1/k)-competitive.

Original language	English (US)
Title of host publication	Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings
Editors	Jaroslav Nešetřil
Publisher	Springer Verlag
Pages	289-300
Number of pages	12
ISBN (Print)	3540662510, 9783540662518
DOIs	https://doi.org/10.1007/3-540-48481-7_26
State	Published - 1999
Event	7th Annual European Symposium on Algorithms, ESA 1999 - Prague, Czech Republic Duration: Jul 16 1999 → Jul 18 1999

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1643
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	7th Annual European Symposium on Algorithms, ESA 1999
Country/Territory	Czech Republic
City	Prague
Period	7/16/99 → 7/18/99

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-48481-7_26

Cite this

Anderson, E. J., Hildrum, K., Karlin, A. R., Rasala, A., & Saks, M. (1999). On list update and work function algorithms. In J. Nešetřil (Ed.), Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings (pp. 289-300). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1643). Springer Verlag. https://doi.org/10.1007/3-540-48481-7_26

Anderson, Eric J. ; Hildrum, Kris ; Karlin, Anna R. et al. / On list update and work function algorithms. Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. editor / Jaroslav Nešetřil. Springer Verlag, 1999. pp. 289-300 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{aed55ecc04cb46d6b8f48b40b4c9d11b,

title = "On list update and work function algorithms",

abstract = "The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has constant competitive ratio for list update. In the process, we present a new formulation of the well-known {"}list factoring{"} technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is (2 — 1/k)-competitive.",

author = "Anderson, {Eric J.} and Kris Hildrum and Karlin, {Anna R.} and April Rasala and Michael Saks",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 7th Annual European Symposium on Algorithms, ESA 1999 ; Conference date: 16-07-1999 Through 18-07-1999",

year = "1999",

doi = "10.1007/3-540-48481-7_26",

language = "English (US)",

isbn = "3540662510",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "289--300",

editor = "Jaroslav Ne{\v s}et{\v r}il",

booktitle = "Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings",

address = "Germany",

}

Anderson, EJ, Hildrum, K, Karlin, AR, Rasala, A & Saks, M 1999, On list update and work function algorithms. in J Nešetřil (ed.), Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1643, Springer Verlag, pp. 289-300, 7th Annual European Symposium on Algorithms, ESA 1999, Prague, Czech Republic, 7/16/99. https://doi.org/10.1007/3-540-48481-7_26

On list update and work function algorithms. / Anderson, Eric J.; Hildrum, Kris; Karlin, Anna R. et al.
Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. ed. / Jaroslav Nešetřil. Springer Verlag, 1999. p. 289-300 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1643).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On list update and work function algorithms

AU - Anderson, Eric J.

AU - Hildrum, Kris

AU - Karlin, Anna R.

AU - Rasala, April

AU - Saks, Michael

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1999.

PY - 1999

Y1 - 1999

N2 - The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has constant competitive ratio for list update. In the process, we present a new formulation of the well-known "list factoring" technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is (2 — 1/k)-competitive.

AB - The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has constant competitive ratio for list update. In the process, we present a new formulation of the well-known "list factoring" technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is (2 — 1/k)-competitive.

UR - http://www.scopus.com/inward/record.url?scp=84958046144&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958046144&partnerID=8YFLogxK

U2 - 10.1007/3-540-48481-7_26

DO - 10.1007/3-540-48481-7_26

M3 - Conference contribution

AN - SCOPUS:84958046144

SN - 3540662510

SN - 9783540662518

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 289

EP - 300

BT - Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings

A2 - Nešetřil, Jaroslav

PB - Springer Verlag

T2 - 7th Annual European Symposium on Algorithms, ESA 1999

Y2 - 16 July 1999 through 18 July 1999

ER -

Anderson EJ, Hildrum K, Karlin AR, Rasala A, Saks M. On list update and work function algorithms. In Nešetřil J, editor, Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. Springer Verlag. 1999. p. 289-300. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-48481-7_26

On list update and work function algorithms

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this