The work function algorithm for the paging problem

DOI10.1016/J.TCS.2022.07.014MaRDI QIDQ2166767zbMATH OpenOpenAlexFDO

Authors W. M. Zhang, Huan Hu, Yongxi Cheng, Haizhen Wang, Hongmei Li

Publication date 25 August 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2022.07.014

zbMATH Keywords

\(k\)-server problemcompetitive analysisonline algorithmpaging problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• A fast work function algorithm for solving the k-server problem
• A new upper bound on the work function algorithm for the k-server problem
• scientific article; zbMATH DE number 1500547
• Page Migration Algorithms Using Work Functions
• Competitive paging algorithms

Cites work

• A fast approximate implementation of the work function algorithm for solving the k-server problem
• A fast work function algorithm for solving the k-server problem
• A new upper bound on the work function algorithm for the k-server problem
• Competitive paging algorithms
• Competitive snoopy caching
• scientific article; zbMATH DE number 65695 (Why is no real title available?)
• On the k -server conjecture
• On the competitive ratio of the work function algorithm for the k-server problem

Cited in

(2)

• Page Migration Algorithms Using Work Functions
• The optimal structure of algorithms for \(\alpha\)-paging

This page was built for publication: The work function algorithm for the paging problem

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