A randomized on–line algorithm for the k–server problem on a line

DOI10.1002/RSA.20124MaRDI QIDQ5486309zbMATH OpenOpenAlexFDO

Authors Béla Csaba, Sachin Lodha

Publication date 6 September 2006

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20124

zbMATH Keywords

\(k\)-server algorithm

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Recommendations

• A randomized algorithm for two servers on the line.
• A polylogarithmic-competitive algorithm for the k-server problem
• scientific article; zbMATH DE number 6469207
• Randomized k-server algorithms for growth-rate bounded graphs
• R-LINE: a better randomized 2-server algorithm on the line

Cites work

• Better algorithms for unfair metrical task systems and applications
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1500547 (Why is no real title available?)
• scientific article; zbMATH DE number 1559591 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• scientific article; zbMATH DE number 1875409 (Why is no real title available?)
• Online algorithms. The state of the art

Cited in

(12)

• Randomized algorithm for the \(k\)-server problem on decomposable spaces
• A primal-dual online algorithm for the k-server problem on weighted HSTs
• A randomized algorithm for two servers on the line.
• R-LINE: a better randomized 2-server algorithm on the line
• A polylogarithmic-competitive algorithm for the k-server problem
• An Optimal On-Line Algorithm for K Servers on Trees
• Randomized memoryless algorithms for the weighted and the generalized k-server problems
• Competitive algorithms for server problems
• scientific article; zbMATH DE number 65696 (Why is no real title available?)
• The harmonic k -server algorithm is competitive
• Breaking the 2-competitiveness barrier for two servers in a tree
• R-LINE: a better randomized 2-server algorithm on the line

This page was built for publication: A randomized on–line algorithm for the k–server problem on a line

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