On online algorithms with advice for the k-server problem

Abstract. We consider the model of online computation with advice [6]. In particular, we study the k-server problem under this model. We prove three upper bounds for this problem. First, we show a dlog ke b−2 competitive online algorithm for general metric spaces with b bits of advice per request, where 3 ≤ b ≤ log k. This improves upon the result of [1]. Moreover, we believe that our algorithm and our analysis are more intuitive and simpler than those of [1]. Second, we give a 1-competitive online algorithm for finite trees which uses 2+2dlog(p+1)e bits of advice per request, where p is the caterpillar dimension of the tree. Lastly, we present a variant of the algorithm for the tree that is optimal for the line with 1-bit of advice