The (h, k)-Server Problem on Bounded Depth Trees

DOI10.1137/1.9781611974782.65MaRDI QIDQ4575805zbMATH OpenOpenAlexFDO

Authors N. Bansal, Marek Eliáš, Łukasz Jeż, Grigorios Koumoutsos

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.08527

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27)

Abstract: We study the $k$-server problem in the resource augmentation setting i.e., when the performance of the online algorithm with $k$ servers is compared to the offline optimal solution with $hleqk$ servers. The problem is very poorly understood beyond uniform metrics. For this special case, the classic $k$-server algorithms are roughly $(1+1/epsilon)$-competitive when $k=(1+epsilon)h$, for any $epsilon>0$. Surprisingly however, no $o(h)$-competitive algorithm is known even for HSTs of depth 2 and even when $k/h$ is arbitrarily large. We obtain several new results for the problem. First we show that the known $k$-server algorithms do not work even on very simple metrics. In particular, the Double Coverage algorithm has competitive ratio $Omega(h)$ irrespective of the value of $k$, even for depth-2 HSTs. Similarly the Work Function Algorithm, that is believed to be optimal for all metric spaces when $k=h$, has competitive ratio $Omega(h)$ on depth-3 HSTs even if $k=2h$. Our main result is a new algorithm that is $O(1)$-competitive for constant depth trees, whenever $k=(1+epsilon)h$ for any $epsilon>0$. Finally, we give a general lower bound that any deterministic online algorithm has competitive ratio at least 2.4 even for depth-2 HSTs and when $k/h$ is arbitrarily large. This gives a surprising qualitative separation between uniform metrics and depth-2 HSTs for the $(h,k)$-server problem, and gives the strongest known lower bound for the problem on general metrics.

Recommendations

• The (h,k)-server problem on bounded depth trees
• An Optimal On-Line Algorithm for K Servers on Trees
• The fast algorithm for online \(k\)-server problem on trees
• The \(k\)-server problem
• On the bicriteria k-server problem
• A general decomposition theorem for the k-server problem
• scientific article; zbMATH DE number 1875409
• On the k -server conjecture
• On the k-server conjecture
• scientific article; zbMATH DE number 6469207

Cited in

(7)

• A primal-dual online algorithm for the k-server problem on weighted HSTs
• Online facility location with mobile facilities
• An Optimal On-Line Algorithm for K Servers on Trees
• The (h,k)-server problem on bounded depth trees
• The Infinite Server Problem
• \(k\)-servers with a smile: online algorithms via projections
• Online \(k\)-taxi via double coverage and time-reverse primal-dual

This page was built for publication: The (h, k)-Server Problem on Bounded Depth Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575805)