A better lower bound on the competitive ratio of the randomized 2-server problem

✍ Scribed by Marek Chrobak; Lawrence L. Larmore; Carsten Lund; Nick Reingold

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 482 KB
• Volume: 63
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00099-9

✦ Synopsis

We present a lower bound of 1 + e-"' z 1.6065 on the competitive ratio of randomized algorithms for the weighted 2-cache problem, which is a special case of the 2-server problem. This improves the previously best known lower bound of e/(e-1) N 1.582 for both problems. @