On Competitive On-Line Paging with Lookahead | Zendy

Dany Breslauer | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research