A better lower bound on the competitive ratio of the randomized 2-server problem

DOI10.1016/S0020-0190(97)00099-9MaRDI QIDQ287141zbMATH OpenOpenAlexFDO

Authors Marek Chrobak, Lawrence L. Larmore, Nick Reingold, C. Lund

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00099-9

zbMATH Keywords

online algorithmsrandomized algorithmscompetitive analysis

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Randomized competitive analysis for two server problems
• Randomized Competitive Analysis for Two-Server Problems
• A randomized algorithm for two servers on the line.
• Lower Bounds for Randomized k-Server and Motion-Planning Algorithms
• A decomposition theorem for task systems and bounds for randomized server problems

Cites work

• scientific article; zbMATH DE number 1003270 (Why is no real title available?)
• scientific article; zbMATH DE number 432776 (Why is no real title available?)
• scientific article; zbMATH DE number 432777 (Why is no real title available?)
• scientific article; zbMATH DE number 1256655 (Why is no real title available?)
• A New Approach to the Server Problem
• A strongly competitive randomized paging algorithm
• An Optimal On-Line Algorithm for K Servers on Trees
• Competitive algorithms for server problems
• Competitive analysis of randomized paging algorithms
• On the \(k\)-server conjecture
• The 2-evader problem

Cited in

(15)

• A Randomized Algorithm for Two Servers in Cross Polytope Spaces
• Breaking the 2-competitiveness barrier for two servers in a tree
• Randomized Competitive Analysis for Two-Server Problems
• scientific article; zbMATH DE number 2038743 (Why is no real title available?)
• Trackless online algorithms for the server problem
• R-LINE: a better randomized 2-server algorithm on the line
• A competitive 2-server algorithm
• Randomized on-line scheduling on two uniform machines
• A randomized algorithm for two servers on the line.
• Optimal algorithms for page migration in dynamic networks
• A general decomposition theorem for the k-server problem
• The weighted 2-server problem
• A randomized algorithm for two servers in cross polytope spaces
• Randomized competitive analysis for two server problems
• Randomized priority algorithms

This page was built for publication: A better lower bound on the competitive ratio of the randomized 2-server problem

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