Thomas Moscibroda, Adele A. Rescigno
1 Computer Science, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU 2 Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU 3 unknown 4 Computer Science, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU
We consider the k-Server problem under the advice model of computation when the underlying metric space is sparse. On one 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))1 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 logN)) 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. On the other 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. © Springer International Publishing 2013.
Lecture Notes in Computer Science: 20th International Colloquium, Sirocco 2013, Ischia, Italy, July 1-3, 2013, Revised Selected Papers, 2013, p. 55-67
Main Research Area:
Lecture Notes in Computer Science
20th International Colloquium on Structural Information & Communication ComplexityColloquium on Structural Information & Communication Complexity, 2013