Randomized algorithm for the \(k\)-server problem on decomposable spaces

DOI10.1016/j.jda.2009.02.005zbMath1192.68861OpenAlexW2067086474MaRDI QIDQ1044025

Judit Nagy-György

Publication date: 10 December 2009

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

Full work available at URL: https://doi.org/10.1016/j.jda.2009.02.005

zbMATH Keywords

metric spaceson-line algorithmsrandomized algorithms\(k\)-serverprobabilistic approximation of metric spaces

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Related Items (1)

R-LINE: a better randomized 2-server algorithm on the line

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly competitive randomized paging algorithm
• A randomized algorithm for the on-line weighted bipartite matching problem
• On the power of randomization in on-line algorithms
• A general decomposition theorem for the \(k\)-server problem
• Ramsey-type theorems for metric spaces with applications to online problems
• On metric Ramsey-type phenomena
• Randomized k-server algorithms for growth-rate bounded graphs
• Competitive algorithms for server problems
• Competitive paging algorithms
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• On the k -server conjecture
• A randomized on–line algorithm for the k–server problem on a line
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Randomized algorithm for the \(k\)-server problem on decomposable spaces