Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
A Randomized Algorithm for Two Servers in Cross Polytope Spaces
verfasst von : Wolfgang Bein, Kazuo Iwama, Jun Kawahara, Lawrence L. Larmore, James A. Oravec
Erschienen in: Approximation and Online Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.
[2] give a
$\frac{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
2,4
. We obtain an algorithm with competitive ratio of
$\frac{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
2,4
.