Randomized k-server algorithms for growth-rate bounded graphs

DOI10.1016/J.JALGOR.2004.06.002MaRDI QIDQ3022753zbMATH OpenOpenAlexFDO

Authors Manor Mendel, Yair Bartal

Publication date 30 June 2005

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jalgor.2004.06.002

zbMATH Keywords

\(k\)-server problemMetric embeddingRandomized algorithms

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Recommendations

• scientific article; zbMATH DE number 6469207
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Randomized algorithm for the \(k\)-server problem on decomposable spaces
• Towards the randomized \(k\)-server conjecture, a primal-dual approach
• Randomized memoryless algorithms for the weighted and the generalized k-server problems
• scientific article; zbMATH DE number 1263228
• Lower Bounds for Randomized k-Server and Motion-Planning Algorithms
• Fully dynamic randomized algorithms for graph spanners
• scientific article; zbMATH DE number 1256655
• The (h,k)-server problem on bounded depth trees

Cited in

(14)

• Randomized algorithm for the \(k\)-server problem on decomposable spaces
• A \(k\)-median based online algorithm for the stochastic \(k\)-server problem
• The \(k\)-resource problem in uniform metric spaces
• More on random walks, electrical networks, and the harmonic \(k\)-server algorithm.
• Competitive analysis for the on-line truck transportation problem
• Ramsey-type theorems for metric spaces with applications to online problems
• A polylogarithmic-competitive algorithm for the k-server problem
• scientific article; zbMATH DE number 65694 (Why is no real title available?)
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Competitive algorithms for generalized k-server in uniform metrics
• A randomized on–line algorithm for the k–server problem on a line
• scientific article; zbMATH DE number 6469207 (Why is no real title available?)
• Fast geographic routing in fixed-growth graphs
• Server problems and resistive spaces

This page was built for publication: Randomized k-server algorithms for growth-rate bounded graphs

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