A better lower bound on the competitive ratio of the randomized 2-server problem
From MaRDI portal
Publication:287141
DOI10.1016/S0020-0190(97)00099-9zbMath1337.68116OpenAlexW1969406444MaRDI QIDQ287141
Marek Chrobak, Lawrence L. Larmore, Nick Reingold, Carstent 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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (14)
The weighted 2-server problem ⋮ Randomized competitive analysis for two server problems ⋮ General caching is hard: even with small pages ⋮ 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 Competitive Analysis for Two-Server Problems ⋮ Randomized on-line scheduling on two uniform machines ⋮ Randomized priority algorithms ⋮ A Randomized Algorithm for Two Servers in Cross Polytope Spaces ⋮ Optimal algorithms for page migration in dynamic networks ⋮ A randomized algorithm for two servers on the line. ⋮ A general decomposition theorem for the \(k\)-server problem ⋮ Trackless online algorithms for the server problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A strongly competitive randomized paging algorithm
- The 2-evader problem
- Competitive analysis of randomized paging algorithms
- On the k-server conjecture
- An Optimal On-Line Algorithm for K Servers on Trees
- Competitive algorithms for server problems
- A New Approach to the Server Problem
This page was built for publication: A better lower bound on the competitive ratio of the randomized 2-server problem
