Name
Abstract | ||
|---|---|---|
The optimal competitive ratio for a randomized online list update algorithm is known to be at least 1.5 and at most 1.6, but the remaining gap is not yet closed. We present a new lower bound of 1.50084 for the partial cost model. The construction is based on game trees with incomplete information, which seem to be generally useful for the competitive analysis of online algorithms. 2001 Elsevier Science B.V. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1016/S0304-3975(00)00257-7 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
randomized online list update,list update problem,game tree,List-update,competitive analysis,Elsevier Science B.V.,partial cost model,online algorithm,remaining gap,incomplete information,Competitive analysis,On-line algorithms,Analysis of algorithms,optimal competitive ratio | Journal | 268 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 7 |
PageRank | References | Authors |
0.51 | 11 | 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 |