Paper detail

On Advice Complexity of the k-server Problem under Sparse Metrics

We consider the k-server problem under the advice model of computation when the underlying metric space is sparse. On one side, we show that an advice of size Ω(n) is required to obtain a 1-competitive algorithm for sequences of size n, even for the 2-server problem on a path metric of size N >= 5. Through another lower bound argument, we show that at least (n/2)(log α - 1.22) bits of advice is required to obtain an optimal solution for metric spaces of treewidth α, where 4 <= α < 2k. On the other side, we introduce Θ(1)-competitive algorithms for a wide range of sparse graphs, which require advice of (almost) linear size. Namely, we show that for graphs of size N and treewidth α, there is an online algorithm which receives $O(n (log α + log log N))$ bits of advice and optimally serves a sequence of length n. With a different argument, we show that if a graph admits a system of μ collective tree (q,r)-spanners, then there is a (q+r)-competitive algorithm which receives O(n (log μ + log log N)) bits of advice. Among other results, this gives a 3-competitive algorithm for planar graphs, provided with O(n log log N) bits of advice.