Optimal Lower Bounds for Projective List Update Algorithms

Details Optimal Lower Bounds for Projective List Update Algorithms Optimal Lower Bounds for Projective List Update Algorithms

2010-02-11

arxiv.org/abs/1002.2440v3

Computer Science

Computational Complexity

Version 3 same as version 2, but date in LaTeX \today macro replaced by March 8, 2012

Scientific paper

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 paper 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.

Affiliated with

Also associated with

No associations

Rating

Optimal Lower Bounds for Projective List Update Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Lower Bounds for Projective List Update Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Lower Bounds for Projective List Update Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-419122