Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2500120 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
list item,competitive ratio,list update problem,list update algorithm,possible projective algorithm,good online algorithm,projective list update algorithm,list factoring,timestamp algorithm ts,lower bound,optimal competitive ratio,competitive analysis,online algorithms | Online algorithm,Combinatorics,List update problem,Algorithm,Theoretical computer science,Timestamp,Self-organizing list,Factoring,Mathematics,Competitive analysis,Projective test | Journal |
Volume | Issue | ISSN |
9 | 4 | ACM Transactions on Algorithms (TALG) Volume 9, Issue 4, September
2013, Article 31, 18 pages |
Citations | PageRank | References |
2 | 0.36 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Ambühl | 1 | 357 | 18.50 |
| Bernd Gärtner | 2 | 461 | 45.50 |
| Bernhard von Stengel | 3 | 275 | 38.51 |