On the advice complexity of the k-server problem

摘要

The model of advice complexity offers an alternative measurement allowing for a more fine-grained analysis of the hardness of online problems than standard competitive analysis. Here, one measures the amount of information an online algorithm is lacking about the yet unrevealed parts of the input. This model was successfully used for many online problems including the k-server problem. We extend the analysis of the k-server problem by giving a lower bound on the advice necessary to obtain optimality, and upper bounds on online algorithms for the general and the Euclidean case. For the general case, we improve the previous results by an exponential factor; for the Euclidean case, we achieve a constant competitive ratio using constantly many advice bits per request. Furthermore, for many online problems, we show how lower bounds on the advice complexity can be transformed into lower bounds on the expected competitive ratio of randomized online algorithms.