Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • On-line algorithms  (1)
Source
Material
Years
Keywords
  • 1
    Electronic Resource
    Electronic Resource
    A strongly competitive randomized paging algorithm (1991)
    Springer
    Algorithmica 6 (1991), S. 816-825 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...