On Online Algorithms with Advice for the k-Server Problem

Abstract

We consider the model of online computation with advice (Emek et al., Theor. Comput. Sci. 412(24): 2642–2656, 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 Böckenhauer et al. (ICALP (1), Lecture Notes in Computer Science, vol. 6755, pp. 207–218, 2011). Moreover, we believe that our algorithm and our analysis are more intuitive and simpler than those of Böckenhauer 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.

Appendix: Minimum Matching

Lemma 3

Let A and B be two sets of points of equal size on the line. For any a∈A there is a minimum weighted matching between the points of A and the points of B such that a is matched to a point b∈B, where b is the first element of B to the right or the left of a.

Proof

Given a minimum weighted matching between the sets A and B on the line, let a∈A be matched to a server e∈B such that e is not the first element of B to the right or the left of a and let b∈B be a point that is the first element of B to the left or the right of a and between a and e on the line. Let c∈A be the point to which b is matched. Let d(x,y) be the distance between the points x and y on the line. Without loss of generality, assume that b and e are to the right of a.

If c is between b and e, then d(a,b)+d(c,e)≤d(a,e)+d(b,c), so a can be matched to b and c can be matched to e without increasing the cost of the matching.

If c is to the right of e, then d(a,b)+d(e,c)≤d(a,e)+d(b,c) since d(a,b)+2d(b,e)+d(e,c)=d(a,e)+d(b,c). So, a can be matched to b and c can be matched to e without increasing the cost of the matching.

If c is to the left of a, then d(a,b)+d(c,e)=d(c,b)+d(a,e) since d(a,b)+d(c,e)=d(a,e)+2d(a,b)+d(c,b)=d(a,b)+d(c,e). So, a can be matched to b and c can be matched to e without increasing the cost of the matching.

The final case is that c is between a and b. Note that this is the previous case with a and c swapped. As in the previous case, a can be matched to b and c can be matched to e without increasing the cost of the matching. □