A lower bound for randomized list update algorithms (Q685486)

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)].