A Polylogarithmic-Competitive Algorithm for the k-Server Problem

DOI10.1109/FOCS.2011.63zbMath1292.68153OpenAlexW2069121074MaRDI QIDQ5494971

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

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.63

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Randomized algorithms (68W20)

Related Items (14)

Serving Online Requests with Mobile Servers ⋮ On the advice complexity of the \(k\)-server problem ⋮ Prioritized Metric Structures and Embedding ⋮ A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ R-LINE: a better randomized 2-server algorithm on the line ⋮ Breaking the 2-competitiveness barrier for two servers in a tree ⋮ Pattern matching under DTW distance ⋮ The \(k\)-server problem with advice in \(d\) dimensions and on the sphere ⋮ The k-Server Problem with Delays on the Uniform Metric Space ⋮ Metrical service systems with multiple servers ⋮ Local embeddings of metric spaces ⋮ Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation ⋮ The fast algorithm for online \(k\)-server problem on trees

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