Randomized competitive analysis for two server problems
From MaRDI portal
Summary: We prove that there exists a randomized online algorithm for the 2-server 3-point problem whose expected competitive ratio is at most 1.5897. This is the first nontrivial upper bound for randomized \(k\)-server algorithms in a general metric space whose competitive ratio is well below the corresponding deterministic lower bound \((= 2\) in the 2-server case).
Recommendations
- Randomized Competitive Analysis for Two-Server Problems
- scientific article; zbMATH DE number 2038743
- A better lower bound on the competitive ratio of the randomized 2-server problem
- A Randomized Algorithm for Two Servers in Cross Polytope Spaces
- A randomized algorithm for two servers in cross polytope spaces
- scientific article; zbMATH DE number 1256655
- A competitive 2-server algorithm
- Competitive k-server algorithms
- Competitive algorithms for server problems
- Randomized algorithm for the \(k\)-server problem on decomposable spaces
Cites work
- A better lower bound on the competitive ratio of the randomized 2-server problem
- A Randomized Algorithm for Two Servers in Cross Polytope Spaces
- A randomized algorithm for two servers on the line.
- An Optimal On-Line Algorithm for K Servers on Trees
- Competitive algorithms for server problems
- Competitive paging algorithms
- Competitive randomized algorithms for nonuniform problems
- Dynamic TCP acknowledgement and other stories about e/(e-1)
- Equitable Revisited
- Finite-State Online Algorithms and Their Automated Competitive Analysis
- Gadgets, Approximation, and Linear Programming
- scientific article; zbMATH DE number 1003270 (Why is no real title available?)
- scientific article; zbMATH DE number 65695 (Why is no real title available?)
- scientific article; zbMATH DE number 3556125 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- New Ressults on Server Problems
- On the k -server conjecture
- On the online bin packing problem
- Random walks on weighted graphs and applications to on-line algorithms
- Randomized competitive algorithms for the list update problem
Cited in
(18)- A competitive 2-server algorithm
- Competitive randomized algorithms for nonuniform problems
- A randomized algorithm for two servers on the line.
- Randomized online computation with high probability guarantees
- Multiple spin-block decisions
- R-LINE: a better randomized 2-server algorithm on the line
- A better lower bound on the competitive ratio of the randomized 2-server problem
- Randomized Competitive Analysis for Two-Server Problems
- Lower Bounds for Randomized k-Server and Motion-Planning Algorithms
- scientific article; zbMATH DE number 2038743 (Why is no real title available?)
- scientific article; zbMATH DE number 742965 (Why is no real title available?)
- The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem
- A Randomized Algorithm for Two Servers in Cross Polytope Spaces
- Breaking the 2-competitiveness barrier for two servers in a tree
- A randomized algorithm for two servers in cross polytope spaces
- Server problems and resistive spaces
- Randomized algorithms for online bounded bidding
- R-LINE: a better randomized 2-server algorithm on the line
This page was built for publication: Randomized competitive analysis for two server problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662430)
