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 wih k extra pages and lookahead l depends on k+l. Hence, under these measures, an on-line algorithm has the same benefit fom using an extra page or knowing an extra bit of the future.
展开▼
