A Polylogarithmic-Competitive Algorithm for the k -Server Problem

DOI10.1145/2783434zbMath1426.68294arXiv1110.1580OpenAlexW2113184918MaRDI QIDQ3177748

Nikhil Bansal, Aleksander Mądry, Joseph (Seffi) Naor, Niv Buchbinder

Publication date: 2 August 2018

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

Full work available at URL: https://arxiv.org/abs/1110.1580

zbMATH Keywords

randomizationcompetitive analysis\(k\)-server problem

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (9)

Metric Embedding via Shortest Path Decompositions ⋮ Competitive Algorithms for Generalized k -Server in Uniform Metrics ⋮ Min-Cost Bipartite Perfect Matching with Delays ⋮ Managing multiple mobile resources ⋮ Multi-Finger Binary Search Trees ⋮ A Combinatorial Metrical Task System Problem Under the Uniform Metric ⋮ Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing ⋮ The fast algorithm for online \(k\)-server problem on trees ⋮ Memoryless algorithms for the generalized k-server problem on uniform metrics

This page was built for publication: A Polylogarithmic-Competitive Algorithm for the k -Server Problem