Improved Randomized on-line Algorithms for the List Update Problem

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

Abstract

The best randomized on-line algorithms known so far for the list update problem achieve a competitiveness of √3 ≈ 1.73. In this paper we present a new family of randomized online algorithms that beat this competitive ratio. Our improved algorithms are called TIMESTAMP algorithms and achieve a competitiveness of max{2 - p, 1 +p(2 - p)}, for any real number p ε [0,1]. Setting p = (3 - √5)/2, we obtain a ø-competitive algorithm, where ø = (1 + √5)/2 ≈ 1.62 is the golden ratio. TIMESTAMP algorithms coordinate the movements of items using some information on past requests. We can reduce the required information at the expense of increasing the competitive ratio. We present a very simple version of the TIMESTAMP algorithms that is 1.68-competitive. The family of TIMESTAMP algorithms also includes a new deterministic 2-competitive on-line algorithm that is different from the MOVE-TO-FRONT rule.

Original languageEnglish
Pages (from-to)682-693
Number of pages12
JournalSIAM Journal on Computing
Volume27
Issue number3
DOIs
StatePublished - 1998
Externally publishedYes

Keywords

  • Competitive analysis
  • Linear lists
  • On-line algorithms

Fingerprint

Dive into the research topics of 'Improved Randomized on-line Algorithms for the List Update Problem'. Together they form a unique fingerprint.

Cite this