On Competitive On-Line Paging with Lookahead

  • Dany Breslauer


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.
How to Cite
Breslauer, D. (1995). On Competitive On-Line Paging with Lookahead. BRICS Report Series, 2(50). https://doi.org/10.7146/brics.v2i50.19951