A polylogarithmic-competitive algorithm for the k-server problem
From MaRDI portal
Publication:3177748
DOI10.1145/2783434zbMATH Open1426.68294arXiv1110.1580OpenAlexW2113184918MaRDI QIDQ3177748FDOQ3177748
N. Bansal, Aleksander Mądry, Joseph (Seffi) Naor, Niv Buchbinder
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 -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
Cited In (14)
- Metric Embedding via Shortest Path Decompositions
- Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing
- Memoryless algorithms for the generalized k-server problem on uniform metrics
- Chasing convex bodies optimally
- 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
- A Combinatorial Metrical Task System Problem Under the Uniform Metric
- Competitive \(k\)-server algorithms
- The \(K\)-server problem via a modern optimization lens
- Online paging with heterogeneous cache slots
- Min-Cost Bipartite Perfect Matching with Delays
- 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)
