Randomized competitive analysis for two server problems (Q1662430)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Randomized competitive analysis for two server problems |
scientific article |
Statements
Randomized competitive analysis for two server problems (English)
0 references
20 August 2018
0 references
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).
0 references
randomized algorithms
0 references
online algorithms
0 references
server problems
0 references
0 references
