2011 | OriginalPaper | Buchkapitel
On the Advice Complexity of the k-Server Problem
verfasst von : Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič
Erschienen in: Automata, Languages and Programming
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
Competitive analysis is the established tool for measuring the output quality of algorithms that work in an online environment. Recently, the model of
advice complexity
has been introduced as an alternative measurement which allows for a more fine-grained analysis of the hardness of online problems. In this model, one tries to measure the amount of information an online algorithm is lacking about the future parts of the input. This concept was investigated for a number of well-known online problems including the
k
-server problem.
In this paper, we first extend the analysis of the
k
-server problem by giving both a lower bound on the advice needed to obtain an optimal solution, and upper bounds on algorithms for the general
k
-server problem on metric graphs and the special case of dealing with the Euclidean plane. In the general case, we improve the previously known results by an exponential factor, in the Euclidean case we design an algorithm which achieves a constant competitive ratio for a very small (i.e., constant) number of advice bits per request.
Furthermore, we investigate the relation between advice complexity and randomized online computations by showing how lower bounds on the advice complexity can be used for proving lower bounds for the competitive ratio of randomized online algorithms.