A randomized algorithm for two servers on the line.

DOI10.1006/inco.1999.2809zbMath1046.68982OpenAlexW2039381785MaRDI QIDQ1854341

Marek Chrobak, Lawrence L. Larmore, Yair Bartal

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1999.2809

zbMATH Keywords

\(k\)-server problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Randomized algorithms (68W20)

Related Items (9)

The weighted 2-server problem ⋮ A fast work function algorithm for solving the \(k\)-server problem ⋮ Randomized competitive analysis for two server problems ⋮ R-LINE: a better randomized 2-server algorithm on the line ⋮ Breaking the 2-competitiveness barrier for two servers in a tree ⋮ A randomized algorithm for two servers in cross polytope spaces ⋮ Randomized on-line scheduling on two uniform machines ⋮ Knowledge state algorithms ⋮ A general decomposition theorem for the \(k\)-server problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A better lower bound on the competitive ratio of the randomized 2-server problem
• A combined BIT and TIMESTAMP algorithm for the list update problem
• A strongly competitive randomized paging algorithm
• Competitive randomized algorithms for nonuniform problems
• The 2-evader problem
• On the k-server conjecture
• An Optimal On-Line Algorithm for K Servers on Trees
• New Ressults on Server Problems
• Competitive algorithms for server problems
• Sequencing Problems in Two-Server Systems
• On the k -server conjecture
• Competitive analysis of randomized paging algorithms
• Randomized algorithms for metrical task systems

This page was built for publication: A randomized algorithm for two servers on the line.