On list update and work function algorithms

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

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations

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, for k the list length.

Original languageEnglish (US)
Pages (from-to)393-418
Number of pages26
JournalTheoretical Computer Science
Volume287
Issue number2
DOIs
StatePublished - Sep 28 2002
EventAlgorthims (ESA'99) - Prague, Czech Republic
Duration: Jul 16 1999Jul 18 1999

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this