Breaking the 2-competitiveness barrier for two servers in a tree

DOI10.1016/j.tcs.2023.114152OpenAlexW4386226759MaRDI QIDQ6052700

Wolfgang W. Bein, Lawrence L. Larmore

Publication date: 17 October 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.114152

zbMATH Keywords

game theoryonline algorithmsrandomized algorithmsT-theoryserver problemtree metric spaces

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 randomized algorithm for two servers in cross polytope spaces
• R-LINE: a better randomized 2-server algorithm on the line
• A canonical decomposition theory for metrics on a finite set
• Randomized competitive analysis for two server problems
• The 3-server problem in the plane.
• A randomized algorithm for two servers on the line.
• \(T\)-theory: An overview
• Ramsey-type theorems for metric spaces with applications to online problems
• Six theorems about injective metric spaces
• Random walks on weighted graphs and applications to on-line algorithms
• An Optimal On-Line Algorithm for K Servers on Trees
• New Ressults on Server Problems
• Competitive algorithms for server problems
• On fast algorithms for two servers
• Competitive paging algorithms
• Beyond Competitive Analysis
• A Primal-Dual Randomized Algorithm for Weighted Paging
• A randomized on–line algorithm for the k–server problem on a line
• A Polylogarithmic-Competitive Algorithm for the k-Server Problem

This page was built for publication: Breaking the 2-competitiveness barrier for two servers in a tree