• Journal of Algorithms 12(4):685-699(1991)

  With Amos Fiat, Richard Karp, Michael Luby, Lyle McGeoch and Daniel Sleator
  The paging problem is that of deciding which pages to keep in a memory of \(k\) pages in order to minimize the number of page faults. This paper introduced the marking algorithm , a randomized on-line algorithm for the paging problem, and a proof that its performance guarantee is \(O(\log k)\). This was one of the first results in the area showing that a randomized algorithm can have a strictly better performance guarantee than any deterministic on-line algorithm (no deterministic on-line algorithm can have a performance guarantee better than k).

  • more...
  •   full text
    
  •   bibtex
    
  •   google scholar
    
  •   doi
    

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.