On list update and work function algorithms

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish (US)
Title of host publicationAlgorithms - ESA 1999 - 7th Annual European Symposium, Proceedings
EditorsJaroslav Nešetřil
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540662510, 9783540662518
StatePublished - 1999
Event7th Annual European Symposium on Algorithms, ESA 1999 - Prague, Czech Republic
Duration: Jul 16 1999Jul 18 1999

Publication series

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


Other7th Annual European Symposium on Algorithms, ESA 1999
Country/TerritoryCzech Republic

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On list update and work function algorithms'. Together they form a unique fingerprint.

Cite this