Randomized competitive analysis for two server problems (Q1662430)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Randomized competitive analysis for two server problems |
scientific article; zbMATH DE number 6920409
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Randomized competitive analysis for two server problems |
scientific article; zbMATH DE number 6920409 |
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
0.9919052
0 references
0.9185079
0 references
0.9117441
0 references
0.9117441
0 references
0 references
0 references
0.8826581
0 references
