A randomized algorithm for two servers in cross polytope spaces
A randomized algorithm for two servers in cross polytope spaces
复制标题
DOI：
10.1016/j.tcs.2010.08.022
复制
发表时间：
2007-10
期刊：
影响因子：
--
通讯作者：
W. Bein;K. Iwama;J. Kawahara;L. Larmore;James A. Oravec
中科院分区：
文献类型：
--
作者：
W. Bein;K. Iwama;J. Kawahara;L. Larmore;James A. Oravec
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 15578 competitive algorithm, but their algorithm is specific to the geometry of the line. We consider here the 2-server problem over Cross Polytope Spaces M24. We obtain an algorithm with competitive ratio of 1912, and show that this ratio is best possible. This algorithm gives the second non-trivial example of metric spaces with better than2-competitive ratio. The algorithm uses a design technique called the knowledge state technique — a method not specific to M24.
