Optimal lower bounds for projective list update algorithms
Authors:
Open Access
- 1 September 2013
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 9 (4) , 1-18
Abstract
The list update problem is a classical online problem, with an optimal competitive ratio that is still open, known to be somewhere between 1.5 and 1.6. An algorithm with competitive ratio 1.6, the smallest known to date, is COMB, a randomized combination of BIT and the TIMESTAMP algorithm TS. This and almost all other list update algorithms, like MTF, are projective in the sense that they can be defined by looking only at any pair of list items at a time. Projectivity (also known as “list factoring”) simplifies both the description of the algorithm and its analysis, and so far seems to be the only way to define a good online algorithm for lists of arbitrary length. In this article, we characterize all projective list update algorithms and show that their competitive ratio is never smaller than 1.6 in the partial cost model. Therefore, COMB is a best possible projective algorithm in this model.Keywords
All Related Versions
Funding Information
- Hasler Stiftung (11099)
- Swiss National Science Foundation
This publication has 11 references indexed in Scilit:
- List Factoring and Relative Worst Order AnalysisLecture Notes in Computer Science, 2011
- Parameterized Analysis of Paging and List Update AlgorithmsLecture Notes in Computer Science, 2010
- A new lower bound for the list update problem in the partial cost modelTheoretical Computer Science, 2001
- Improved Randomized On-Line Algorithms for the List Update ProblemSIAM Journal on Computing, 1998
- Self-organizing data structures1998
- A combined BIT and TIMESTAMP algorithm for the list update problemInformation Processing Letters, 1995
- Randomized competitive algorithms for the list update problemAlgorithmica, 1994
- A lower bound for randomized list update algorithmsInformation Processing Letters, 1993
- Amortized analyses of self-organizing sequential search heuristicsCommunications of the ACM, 1985
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985