摘要：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 look-ahead, or in other words, some partial knowledge of the future. The paper considers a new measure for the look-ahead size as well as Young's resource-bounded look-ahead and proves that both measures have the attractive property that the competitive efficiency of an on-line algorithm with k extra pages and look-ahead l depends on k+l. Hence, under these measures, an on-line algorithm has the same benefit from using an extra page or knowing an extra bit of the future.
