✦ LIBER ✦

Tight Bounds on the Competitive Ratio on Accommodating Sequences for the Seat Reservation Problem

✍ Scribed by Eric Bach; Joan Boyar; Leah Epstein; Lene M. Favrholdt; Tao Jiang; Kim S. Larsen; Guo-Hui Lin; Rob van Stee

Book ID: 110430278
Publisher: Springer US
Year: 2003
Tongue: English
Weight: 238 KB
Volume: 6
Category: Article
ISSN: 1094-6136
DOI: 10.1023/a:1022985808959

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A better lower bound on the competitive

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

✍ Marek Chrobak; Lawrence L. Larmore; Carsten Lund; Nick Reingold 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 482 KB

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. @

On the competitive ratio of the work fun

On the competitive ratio of the work function algorithm for the k-server problem

✍ Yair Bartal; Elias Koutsoupias 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 209 KB

On a bound for the D0L sequence equivale

On a bound for the D0L sequence equivalence problem

✍ A. Ehrenfeucht; G. Rozenberg 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 347 KB

On sequencing with earliest starts and d

On sequencing with earliest starts and due dates with application to computing bounds for the (n/m/G/Fmax) problem

✍ Paul Bratley; Michael Florian; Pierre Robillard 📂 Article 📅 1973 🏛 John Wiley and Sons 🌐 English ⚖ 585 KB