Open AccessOn Competitive On-Line Paging with Lookahead
Author(s) -
Dany Breslauer
Publication year - 1995
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v2i50.19951
Subject(s) - paging , competitive analysis , line (geometry) , computer science , measure (data warehouse) , arithmetic , bounded function , property (philosophy) , algorithm , mathematics , computer network , upper and lower bounds , data mining , mathematical analysis , philosophy , geometry , epistemology
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.