A better lower bound on the competitive ratio of the randomized 2-server problem
DOI10.1016/S0020-0190(97)00099-9zbMATH Open1337.68116OpenAlexW1969406444MaRDI QIDQ287141FDOQ287141
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
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
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)
Cites Work
- The 2-evader problem
- Competitive analysis of randomized paging algorithms
- On the \(k\)-server conjecture
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An Optimal On-Line Algorithm for K Servers on Trees
- Competitive algorithms for server problems
- A New Approach to the Server Problem
- Title not available (Why is that?)
- A strongly competitive randomized paging algorithm
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
- Title not available (Why is that?)
- Trackless online algorithms for the server problem
- R-LINE: a better randomized 2-server algorithm on the line
- Randomized on-line scheduling on two uniform machines
- A competitive 2-server algorithm
- 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)
