A lower bound for randomized list update algorithms
type: Item
instance of: scholarly article
title: A lower bound for randomized list update algorithms
zbMATH Open document ID: 0794.68070
DOI: 10.1016/0020-0190(93)90150-8
author: Boris Teia
published in: Information Processing Letters
publication date: 1993-10-17T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 417397
zbMATH Keywords: list update algorithms
zbMATH Keywords: lower bounds
zbMATH Keywords: randomized algorithms
reviewed by: Mirko Křivánek
MaRDI profile type: Publication
full work available at URL: 0020-0190(93)90150-8
OpenAlex ID: W2006254254
cites work: Two results on the list update problem
cites work: Q3138960
Recommended article: Randomized competitive algorithms for the list update problem
Recommended article: The list update problem: Improved bounds for the counter scheme
Recommended article: Improved Randomized On-Line Algorithms for the List Update Problem
Recommended article: Q4886073
Recommended article: Optimal lower bounds for projective list update algorithms
Recommended article: A new lower bound for the list update problem in the partial cost model
Recommended article: A new family of randomized algorithms for list accessing
Recommended article: Off-line algorithms for the list update problem
Recommended article: Q4542540
Recommended article: Lower time bounds for randomized computation
description: scientific article; zbMATH DE number 417397