A randomized algorithm for two servers in cross polytope spaces

It has been a long-standing open problem to determine the exact randomized competitiveness of the 2 -server problem, that is, the minimum competitiveness of any randomized online algorithm for the 2 -server problem. For deterministic algorithms the best competitive ratio that can be obtained is 2 and no randomized algorithm is known that improves this ratio for general spaces. For the line, Bartal et al. (1998) [2] give a 155 78 competitive algorithm, but their algorithm is specific to the geometry of the line. We consider here the 2 -server problem over Cross Polytope Spaces M 24. We obtain an algorithm with competitive ratio of 19 12, and show that this ratio is best possible. This algorithm gives the second non-trivial example of metric spaces with better than 2 -competitive ratio. The algorithm uses a design technique called the knowledge state technique — a method not specific to M 24.

Authors

• Wolfgang Bein
• Kazuo Iwama
• Jun Kawahara
• Lawrence L. Larmore
• James A. Oravec

Keywords

• Online algorithms
• Randomized algorithms
• Cross polytope spaces
• Server problem
• Algorithm design
• Algorithm engineering