On Online Algorithms with Advice for the k-Server Problem
We consider the model of online computation with advice (Emek et al., Theor. Comput. Sci. 412(24): 26422656, 2011). In particular, we study the k-server problem under this model. We prove three upper bounds for this problem. First, we show a \(\lceil\frac{\lceil\log k\rceil}{b-2}\rceil\)-competitive online algorithm for general metric spaces with b bits of advice per request, where 3?b?logk. This improves upon the result of Bckenhauer et al. (ICALP (1), Lecture Notes in Computer Science, vol. 6755, pp. 207218, 2011). Moreover, we believe that our algorithm and our analysis are more intuitive and simpler than those of Bckenhauer et al. Second, we give a 1-competitive online algorithm for finite trees which uses 2+2?log(p+1)? 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.
online algorithms k-server problem online computation with advice competitive analysis