A Polylogarithmic-Competitive Algorithm for the k-Server Problem

DOI10.1109/FOCS.2011.63MaRDI QIDQ5494971zbMATH OpenOpenAlexFDO

Authors N. Bansal, Niv Buchbinder, Aleksander Mądry, Joseph (Seffi) Naor

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

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

Cited in

(16)

• The fast algorithm for online \(k\)-server problem on trees
• Metrical service systems with multiple servers
• R-LINE: a better randomized 2-server algorithm on the line
• The k-Server Problem with Delays on the Uniform Metric Space
• Improved and deterministic online service with deadlines or delay
• A technique to obtain hardness results for randomized online algorithms -- a survey
• Adversarial bandits with knapsacks
• Local embeddings of metric spaces
• A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs
• Breaking the 2-competitiveness barrier for two servers in a tree
• Time efficient implementation for online \(k\)-server problem on trees
• The \(k\)-server problem with advice in \(d\) dimensions and on the sphere
• Deterministic 3-server on a circle and the limitation of canonical potentials
• Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
• Pattern matching under DTW distance
• On the advice complexity of the \(k\)-server problem

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

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