Unbounded lower bound for k-server against weak adversaries

Conference item

We study the resource augmented version of the k-server problem, also known as the k-server problem against weak adversaries or the (h,k)-server problem. In this setting, an online algorithm using k servers is compared to an offline algorithm using h servers, where h ≤ k. For uniform metrics, it has been known since the seminal work of Sleator and Tarjan (1985) that for any є>0, the competitive ratio drops to a constant if k=(1+є) · h. This result was later generalized to weighted stars (Young 1994) and trees of bounded depth (Bansal et al. 2017). The main open problem for this setting is whether a similar phenomenon occurs on general metrics. We resolve this question negatively. With a simple recursive construction, we show that the competitive ratio is at least Ω(loglogh), even as k→∞. Our lower bound holds for both deterministic and randomized algorithms. It also disproves the existence of a competitive algorithm for the infinite server problem on general metrics.

Authors: Bienkowski, M; Byrka, J; Coester, C; Jeż, L

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Host title: STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
• Pages: 1165-1169
• Publication date: 2020-06-22
• Event title: STOC 2020: 52nd Annual ACM Symposium on Theory of Computing
• Event location: Chicago, IL, USA
• Event website: http://acm-stoc.org/stoc2020/index.html
• Event start date: 2020-06-22
• Event end date: 2020-06-26
• DOI: 10.1145/3357713.3384306
• ISSN: 0737-8017
• ISBN: 9781450369794
• Language: English
• Keywords: resource augmentation; online algorithms; FFR; k-server; weak adversaries