The harmonic k -server algorithm is competitive

DOI10.1145/331605.331606zbMath1094.68538OpenAlexW2051069559MaRDI QIDQ5487824

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

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

Related Items (15)

A simple analysis of the harmonic algorithm for two servers ⋮ 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 ⋮ A fast work function algorithm for solving the \(k\)-server problem ⋮ The ANTS problem ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ The \(k\)-server problem ⋮ A \(k\)-server problem with parallel requests and unit distances ⋮ The \(K\)-server problem via a modern optimization lens ⋮ Metrical service systems with multiple servers ⋮ A lower bound on the competitivity of memoryless algorithms for a generalization of the CNN problem ⋮ Multi-Finger Binary Search Trees ⋮ More on random walks, electrical networks, and the harmonic \(k\)-server algorithm. ⋮ Memoryless algorithms for the generalized k-server problem on uniform metrics

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