More on randomized on-line algorithms for caching.
type: Item
instance of: scholarly article
title: More on randomized on-line algorithms for caching.
zbMATH Open document ID: 1044.68166
DOI: 10.1016/S0304-3975(02)00045-2
author: Marek Chrobak
author: Elias Koutsoupias
author: J. Noga
published in: Theoretical Computer Science
publication date: 2003-08-17T00:00:00Z
review text: We address the tradeoff between the competitive ratio and the resources used by randomized on-line algorithms for caching. Two algorithms reported in the literature that achieve the optimal ratio \(H_k\) require a lot of memory and perform extensive computation at each step. On the other hand a very simple algorithm called RMARK has competitive ratio \(2H_k-1\) within a factor of 2 of the optimum. A natural question that arises here is whether there is a tradeoff between simplicity and the competitive ratio. In particular, is it possible to achieve a competitive ratio better than \(2H_k-1\) with a simple algorithm like RMARK? We first consider marking algorithms that are natural generalizations of RMARK and we prove that for any \({\varepsilon}>0\) there is no randomized marking algorithm for caching with competitive ratio \((2-{\varepsilon})H_k\). Thus RMARK is essentially optimal among marking algorithms. Another model of simple caching algorithms is that of trackless algorithms. These are algorithms that do not store any information about items that are not in the cache. It is known that for \(k=2\) there is no randomized trackless algorithm for caching with ratio better than \(\frac{37}{24}{\approx}1.5416\). The trivial upper bound is 2 achieved even by deterministic algorithms LRU and FIFO. We reduce this gap by giving a trackless randomized algorithm with competitive ratio \({\frac 1 4}(3+\sqrt{13}){\approx}1.6514\).
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 1965245
MaRDI profile type: Publication
cites work: Competitive analysis of randomized paging algorithms
cites work: Limited bookmark randomized online algorithms for the paging problem
cites work: Trackless online algorithms for the server problem
cites work: Q4223058
cites work: An Optimal On-Line Algorithm for K Servers on Trees
cites work: Competitive paging algorithms
cites work: On the k -server conjecture
cites work: Beyond Competitive Analysis
cites work: Competitive algorithms for server problems
cites work: A strongly competitive randomized paging algorithm
cites work: Q4131340
cites work: On-Line Paging Against Adversarially Biased Random Inputs
full work available at URL: s0304-3975(02)00045-2
OpenAlex ID: W2088826026
description: scientific article; zbMATH DE number 1965245