A polylogarithmic-competitive algorithm for the k-server problem

DOI10.1145/2783434zbMATH Open1426.68294arXiv1110.1580OpenAlexW2113184918MaRDI QIDQ3177748FDOQ3177748

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

Publication date: 2 August 2018

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

Abstract: We give the first polylogarithmic-competitive randomized online algorithm for the $k$-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of O(log^3 n log^2 k log log n) for any metric space on n points. Our algorithm improves upon the deterministic (2k-1)-competitive algorithm of Koutsoupias and Papadimitriou [J.ACM'95] whenever n is sub-exponential in k.

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

Recommendations

• Competitive \(k\)-server algorithms
• Randomized k-server algorithms for growth-rate bounded graphs
• A randomized on–line algorithm for the k–server problem on a line
• scientific article; zbMATH DE number 6469207
• Competitive algorithms for generalized \(k\)-server in uniform metrics

zbMATH Keywords

randomizationcompetitive analysis\(k\)-server problem

Mathematics Subject Classification ID

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

Cited In (26)

• Metric Embedding via Shortest Path Decompositions
• \(k\)-server via multiscale entropic regularization
• A Randomized Algorithm for Two Servers in Cross Polytope Spaces
• Memoryless algorithms for the generalized k-server problem on uniform metrics
• Metrical task systems on trees via mirror descent and unfair gluing
• Min-cost bipartite perfect matching with delays
• The \(k\)-resource problem in uniform metric spaces
• The harmonic k -server algorithm is competitive
• Chasing convex bodies optimally
• A \(k\)-median based online algorithm for the stochastic \(k\)-server problem
• A randomized on–line algorithm for the k–server problem on a line
• A combinatorial metrical task system problem under the uniform metric
• Competitive Algorithms for Generalized k -Server in Uniform Metrics
• Multi-Finger Binary Search Trees
• Managing multiple mobile resources
• Time efficient implementation for online \(k\)-server problem on trees
• Competitive \(k\)-server algorithms
• A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs
• Competitive algorithms for generalized \(k\)-server in uniform metrics
• The Online Transportation Problem: On the Exponential Boost of One Extra Server
• The \(K\)-server problem via a modern optimization lens
• Online paging with heterogeneous cache slots
• The online \(k\)-server problem with max-distance objective
• Towards the randomized \(k\)-server conjecture, a primal-dual approach
• The k-Resource Problem on Uniform and on Uniformly Decomposable Metric Spaces
• 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

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