Improved randomized on-line algorithms for the list update problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

18 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
Title of host publicationProceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
PublisherAssociation for Computing Machinery
Pages412-419
Number of pages8
ISBN (Electronic)0898713498
StatePublished - 22 Jan 1995
Externally publishedYes
Event6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 - San Francisco, United States
Duration: 22 Jan 199524 Jan 1995

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Country/TerritoryUnited States
CitySan Francisco
Period22/01/9524/01/95

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