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

(17)

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

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)