Since 2014
On Competitive On-Line Paging with Lookahead
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
On Competitive On-Line Paging with Lookahead
|
|
| Creator |
Breslauer, Dany
|
|
| Description |
This paper studies two methods for improving the competitive efficiency of on-line paging algorithms: in the first, the on-line algorithm canuse more pages; in the second, it is allowed to have a look-ahead, or inother words, some partial knowledge of the future. The paper considers anew measure for the look-ahead size as well as Young's resource-boundedlook-ahead and proves that both measures have the attractive propertythat the competitive efficiency of an on-line algorithm with k extra pagesand look-ahead l depends on k+l. Hence, under these measures, an on-linealgorithm has the same benefit from using an extra page or knowing anextra bit of the future.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
1995-09-20
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/19951
10.7146/brics.v2i50.19951 |
|
| Source |
BRICS Report Series; No 50 (1995): RS-50 On Competitive On-Line Paging with Lookahead
BRICS Report Series; No 50 (1995): RS-50 On Competitive On-Line Paging with Lookahead 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/19951/17604
|
|
| Rights |
Copyright (c) 2015 BRICS Report Series
|
|