The harmonic k -server algorithm is competitive

DOI10.1145/331605.331606MaRDI QIDQ5487824zbMATH OpenOpenAlexFDO

Authors Edward F. Grove, Yair Bartal

Publication date 12 September 2006

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/331605.331606

zbMATH Keywords

generalization of paging problemsHarmonic \(k\)-server algorithm

Mathematics Subject Classification ID

Theory of operating systems (68N25) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• A simple analysis of the harmonic algorithm for two servers
• scientific article; zbMATH DE number 1962818
• HARMONIC is 3-competitive for two servers
• A randomized on–line algorithm for the k–server problem on a line
• A polylogarithmic-competitive algorithm for the k-server problem

Cited in

(23)

• HARMONIC is 3-competitive for two servers
• A primal-dual online algorithm for the k-server problem on weighted HSTs
• The K-server problem via a modern optimization lens
• More on random walks, electrical networks, and the harmonic \(k\)-server algorithm.
• The weighted 2-server problem
• On the competitive ratio of the work function algorithm for the k-server problem
• The CNN problem and other k-server variants
• Memoryless algorithms for the generalized k-server problem on uniform metrics
• Metrical service systems with multiple servers
• The ANTS problem
• A \(k\)-server problem with parallel requests and unit distances
• A lower bound on the competitivity of memoryless algorithms for a generalization of the CNN problem
• A simple analysis of the harmonic algorithm for two servers
• A fast work function algorithm for solving the k-server problem
• Randomized memoryless algorithms for the weighted and the generalized k-server problems
• scientific article; zbMATH DE number 65696 (Why is no real title available?)
• Generosity Helps or an 11-Competitive Algorithm for Three Servers
• scientific article; zbMATH DE number 1962818 (Why is no real title available?)
• The \(k\)-server problem
• scientific article; zbMATH DE number 742965 (Why is no real title available?)
• scientific article; zbMATH DE number 1446755 (Why is no real title available?)
• Multi-Finger Binary Search Trees
• STACS 2004

This page was built for publication: The harmonic k -server algorithm is competitive

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