On Competitive On-Line Paging with Lookahead

Abstract

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.