On Online Algorithms with Advice for the k-Server Problem

One of the most studied online problems is the k-Server Problem which consists of a metric space, k mobile servers and a request sequence, where each request is for a node of the metric space. At the time of the request, if a node is not covered, one of the k servers must be moved to the node. The goal is to minimize the distance traveled by the k servers over the entire request sequence.

Emek, Fraigniaud, Korman and Rosen (ICALP 2009) presented a model of online computation with advice, where, along with each request, an algorithm has access to a quantified amount of information about the future. We present an algorithm that is \lceil(log k)\rceil/(b-1)\rceil, where 3 <= b <= log k, which improves on previous results. More importantly, we present an algorithm and analysis that is more intuitive and simpler than previous ones. Further, we give a 1-competitive algorithm with 2+2\lceil(log p + 1)\rceil bits of advice, where p is the caterpillar dimension of the tree. Lastly, we present an optimal algorithm for the line with 1 bit of advice.