A BETTER LOWER-BOUND ON THE COMPETITIVE RATIO OF THE RANDOMIZED 2-SERVER PROBLEM

Authors
CHROBAK M LARMORE LL LUND C REINGOLD N
Citation
M. Chrobak et al., A BETTER LOWER-BOUND ON THE COMPETITIVE RATIO OF THE RANDOMIZED 2-SERVER PROBLEM, Information processing letters, 63(2), 1997, pp. 79-83
Citations number
12
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
63
Issue
2
Year of publication
1997
Pages
79 - 83
Database
ISI
SICI code
0020-0190(1997)63:2<79:ABLOTC>2.0.ZU;2-6
Abstract
We present a lower bound of 1 + e(-1/2) approximate to 1.6065 on the c ompetitive ratio of randomized algorithms for the weighted 2-cache pro blem, which is a special case of the 2-server problem. This improves t he Previously best known lower bound of e/(e-1) approximate to 1.582 f or both problems. (C) 1997 Elsevier Science B.V.