Randomized Competitive Analysis for Two Server Problems

Randomized Competitive Analysis for Two Server Problems

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...

Full description

Bibliographic Details
Main Authors: Jun Kawahara, Kazuo Iwama, Wolfgang Bein
Format: Article
Language:English
Published: MDPI AG 2008-09-01
Series:Algorithms
Subjects:
Randomized Algorithms
Online Algorithms
Server Problems
Online Access:http://www.mdpi.com/1999-4893/1/1/30/

Internet

http://www.mdpi.com/1999-4893/1/1/30/

Similar Items