𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On competitive on-line paging with lookahead

✍ Scribed by Dany Breslauer

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
833 KB
Volume
209
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

This paper studies two methods for improving the competitive efficiency of on-line paging algorithms: in the first, the on-line algorithm can use more pages; in the second, it is allowed to have a lookahead, or in other words, some partial knowledge of the future. The paper considers a new measure for the lookahead size as well as Young's resource-bounded lookahead and proves that both measures have the attractive property that the competitive efficiency of an on-line algorithm with k extra pages and lookahead 1 depends on k + 1. Hence, under these measures, an on-line algorithm has the same benefit from using an extra page or knowing an extra bit of the fnture.

πŸ“œ SIMILAR VOLUMES

On-Line Paging Against Adversarially Bia
On-Line Paging Against Adversarially Biased Random Inputs
✍ Neal E. Young πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 128 KB

In evaluating an algorithm, worst-case analysis can be overly pessimistic. Average-case analysis can be overly optimistic. An intermediate approach shows that an algorithm does well on a broad class of input distributions. E. Koutsoupias and C. Ε½ H. Papadimitriou 1994, in ''Proc. of the 35th IEEE An

Competitive On-line Scheduling of Contin
Competitive On-line Scheduling of Continuous-Media Streams
✍ Minos Garofalakis; Yannis Ioannidis; Banu Γ–zden; Avi Silberschatz πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 277 KB

within a small constant factor of log D (i.e., they are provably near-optimal) if r < 1/Klog DL; and (4) we introduce a novel admission control policy that partitions the server bandwidth based on the expected popularities of different request lengths and experimentally demonstrate its benefits comp

Average competitive ratios of on-line sp
Average competitive ratios of on-line spanning trees
✍ Feng Bao; Aohan Mei; Yoshihide Igarashi πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 284 KB

We study the average competitive ratio of on-line spanning trees with the same distribution of points in the Euclidean plane. We show a distribution of n points such that the average competitive ratio of on-line spanning trees by any on-line algorithm cannot be less than 4 In n -f . @ 1997 Elsevier

Competitive analysis of incentive compat
Competitive analysis of incentive compatible on-line auctions
✍ Ron Lavi; Noam Nisan πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 322 KB

This paper studies auctions in a setting where the di erent bidders arrive at di erent times and the auction mechanism is required to make decisions about each bid as it is received. Such settings occur in computerized auctions of computational resources as well as in other settings. We call such au