Nordic Journal of Computing Bibliography

Steven S. Seiden. Randomized Online Multi-Threaded Paging. Nordic Journal of Computing, 6(2):148-161, Summer 1999.

We present the first randomized upper and lower bounds for online multi-threaded paging as introduced by Feuerstein and Strejilevich de Loma [1996]. Our main result is a O(w log k)-competitive algorithm for unfair infinite multi-threaded paging, which is optimal to within a constant factor. We also present algorithms and lower bounds for three other sub-models of multi-threaded paging.

Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]

Additional Key Words and Phrases: online algorithms, paging, competitive analysis

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database