Strongly Competitive Algorithms for Paging with Locality of Reference

DOI10.1137/S0097539792236353zbMath0856.68075OpenAlexW2073713788MaRDI QIDQ4887013

Anna R. Karlin, Sandy Irani, Steven J. Phillips

Publication date: 3 February 1997

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539792236353

zbMATH Keywords

optimal algorithmspaging algorithmstructured program graphsundirected access graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (13)

Quantifying Competitiveness in Paging with Locality of Reference ⋮ Randomized online multi-threaded paging ⋮ Strongly competitive algorithms for caching with pipelined prefetching ⋮ On the separation and equivalence of paging strategies and other online algorithms ⋮ Least-recently-used caching with dependent requests ⋮ On paging with locality of reference ⋮ Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis ⋮ On Certain New Models for Paging with Locality of Reference ⋮ Quantifying competitiveness in paging with locality of reference ⋮ On the competitiveness of the move-to-front rule ⋮ A Survey of Algorithms and Models for List Update ⋮ Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities ⋮ Unnamed Item

This page was built for publication: Strongly Competitive Algorithms for Paging with Locality of Reference