Strongly Competitive Algorithms for Paging with Locality of Reference

DOI10.1137/S0097539792236353MaRDI QIDQ4887013zbMATH OpenOpenAlexFDO

Authors Sandy Irani, Anna R. Karlin, 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)

Recommendations

• scientific article; zbMATH DE number 742969
• Quantifying competitiveness in paging with locality of reference
• Competitive paging with locality of reference
• Competitive paging algorithms
• scientific article; zbMATH DE number 1263239

Cited in

(20)

• Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities
• On the competitiveness of the move-to-front rule
• Quantifying competitiveness in paging with locality of reference
• Competitive paging with locality of reference
• Strongly competitive algorithms for caching with pipelined prefetching
• A Survey of Algorithms and Models for List Update
• Quantifying competitiveness in paging with locality of reference
• scientific article; zbMATH DE number 65707 (Why is no real title available?)
• Memory Paging for Connectivity and Path Problems in Graphs
• scientific article; zbMATH DE number 1263239 (Why is no real title available?)
• scientific article; zbMATH DE number 742969 (Why is no real title available?)
• The optimal structure of algorithms for \(\alpha\)-paging
• Randomized online multi-threaded paging
• Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis
• On Certain New Models for Paging with Locality of Reference
• Outperforming LRU via competitive analysis on parametrized inputs for paging
• On paging with locality of reference
• On the separation and equivalence of paging strategies and other online algorithms
• Distributional online weighted paging with limited horizon
• Least-recently-used caching with dependent requests

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4887013)