ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

A strongly competitive randomized paging algorithm (1991)

McGeoch, Lyle A. ; Sleator, Daniel D.

Springer

Algorithmica 6 (1991), S. 816-825

add to mindlist on the mindlist

Details

ISSN: 1432-0541

Keywords: Competitive algorithms ; On-line algorithms ; Paging

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract Thepaging problem is that of deciding which pages to keep in a memory ofk pages in order to minimize the number of page faults. We develop thepartitioning algorithm, a randomized on-line algorithm for the paging problem. We prove that its expected cost on any sequence of requests is within a factor ofH k of optimum. (H k is thekth harmonic number, which is about ln(k).) No on-line algorithm can perform better by this measure. Our result improves by a factor of two the best previous algorithm.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01759073

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit