Improved Randomized on-line Algorithms for the List Update Problem

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

44 Zitate (Scopus)

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.

OriginalspracheEnglisch
Seiten (von - bis)682-693
Seitenumfang12
FachzeitschriftSIAM Journal on Computing
Jahrgang27
Ausgabenummer3
DOIs
PublikationsstatusVeröffentlicht - 1998
Extern publiziertJa

Fingerprint

Untersuchen Sie die Forschungsthemen von „Improved Randomized on-line Algorithms for the List Update Problem“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren