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

DOI10.1016/J.TCS.2015.08.043MaRDI QIDQ888438zbMATH OpenOpenAlexFDO

Authors Lucas Bang, Lawrence L. Larmore, Wolfgang W. Bein

Publication date 30 October 2015

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

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

zbMATH Keywords

game theoryonline algorithmsrandomized algorithmsalgorithm designT-theoryserver problem

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Applications of game theory (91A80)

Recommendations

• R-LINE: a better randomized 2-server algorithm on the line
• A randomized algorithm for two servers on the line.
• Randomized Competitive Analysis for Two-Server Problems
• Randomized competitive analysis for two server problems
• A randomized on–line algorithm for the k–server problem on a line

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A Polylogarithmic-Competitive Algorithm for the k-Server Problem
• A better lower bound on the competitive ratio of the randomized 2-server problem
• A canonical decomposition theory for metrics on a finite set
• A primal-dual randomized algorithm for weighted paging
• A randomized algorithm for two servers in cross polytope spaces
• A randomized algorithm for two servers on the line.
• A randomized on–line algorithm for the k–server problem on a line
• An Optimal On-Line Algorithm for K Servers on Trees
• Beyond Competitive Analysis
• Classification of six-point metrics
• Competitive algorithms for server problems
• Game Theory
• Knowledge state algorithms
• New Ressults on Server Problems
• On fast algorithms for two servers
• Optimal online buffer scheduling for block devices
• Ramsey-type theorems for metric spaces with applications to online problems
• Random walks on weighted graphs and applications to on-line algorithms
• Randomized algorithm for the \(k\)-server problem on decomposable spaces
• Randomized competitive analysis for two server problems
• Six theorems about injective metric spaces
• The 3-server problem in the plane.
• The coherency index
• \(T\)-theory: An overview

Cited in

(4)

• R-LINE: a better randomized 2-server algorithm on the line
• A simple algorithm for r-gatherings on the line
• Breaking the 2-competitiveness barrier for two servers in a tree
• A randomized algorithm for two servers on the line.

This page was built for publication: R-LINE: a better randomized 2-server algorithm on the line

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