Randomized competitive analysis for two server problems
type: Item
instance of: scholarly article
title: Randomized competitive analysis for two server problems
zbMATH Open document ID: 1445.68339
author: Kazuo Iwama
author: Jun Kawahara
author: Wolfgang W. Bein
published in: Algorithms
publication date: 2018-08-20T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 68W27
zbMATH DE Number: 6920409
zbMATH Keywords: randomized algorithms
zbMATH Keywords: online algorithms
zbMATH Keywords: server problems
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a1010030
OpenAlex ID: W1967323656
cites work: Competitive algorithms for server problems
cites work: On the k -server conjecture
cites work: New Ressults on Server Problems
cites work: An Optimal On-Line Algorithm for K Servers on Trees
cites work: Random walks on weighted graphs and applications to on-line algorithms
cites work: Competitive randomized algorithms for nonuniform problems
cites work: A better lower bound on the competitive ratio of the randomized 2-server problem
cites work: A randomized algorithm for two servers on the line.
cites work: A Randomized Algorithm for Two Servers in Cross Polytope Spaces
cites work: Equitable Revisited
cites work: Q3128899
cites work: Dynamic TCP acknowledgement and other stories about e/(e-1)
cites work: Randomized competitive algorithms for the list update problem
cites work: Competitive paging algorithms
cites work: Q4128618
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Gadgets, Approximation, and Linear Programming
cites work: On the online bin packing problem
cites work: Finite-State Online Algorithms and Their Automated Competitive Analysis
cites work: Q4010306
DOI: 10.3390/A1010030
Recommended article: Randomized Competitive Analysis for Two-Server Problems
Recommended article: Q4449208
Recommended article: A better lower bound on the competitive ratio of the randomized 2-server problem
Recommended article: A Randomized Algorithm for Two Servers in Cross Polytope Spaces
Recommended article: A randomized algorithm for two servers in cross polytope spaces
Recommended article: Q4230341
Recommended article: A competitive 2-server algorithm
Recommended article: Competitive \(k\)-server algorithms
Recommended article: Competitive algorithms for server problems
Recommended article: Randomized algorithm for the \(k\)-server problem on decomposable spaces
description: scientific article; zbMATH DE number 6920409