A polylogarithmic-competitive algorithm for the k-server problem

DOI10.1145/2783434MaRDI QIDQ3177748zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

\(k\)-server problemcompetitive analysisrandomization

Mathematics Subject Classification ID

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

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.

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

Cited in

(30)

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

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)