A lower bound for randomized list update algorithms (Q685486)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A lower bound for randomized list update algorithms |
scientific article; zbMATH DE number 417397
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A lower bound for randomized list update algorithms |
scientific article; zbMATH DE number 417397 |
Statements
A lower bound for randomized list update algorithms (English)
0 references
17 October 1993
0 references
The author deals with randomized online algorithms for a static list update problem. As a main result it is shown that 1.5 competitiveness presents a lower bound for such algorithms, i.e., the expected cost of any sequence of requests is no more than 1.5 times the cost of an optimal off-line algorithm. The original research is combined with an older result of \textit{A. C. Yao} [Probabilistic computations: Towards a unified measure of complexity, Proc. 18th. Symp. on Foundation of Computer Science, 222-227 (1977)].
0 references
list update algorithms
0 references
lower bounds
0 references
randomized algorithms
0 references
0.9313799
0 references
0.9151597
0 references
0.91339165
0 references
0.90634555
0 references
0.89964914
0 references
0.88453376
0 references
0.8772931
0 references
0.8658382
0 references
