The (H, k)-server problem on bounded depth trees

Nikhil Bansal; Marek Eliáš; Łukasz Jeż; Grigorios Koumoutsos

doi:10.1145/3301314

The (H, k)-server problem on bounded depth trees

Nikhil Bansal, Marek Eliáš, Łukasz Jeż, Grigorios Koumoutsos

Discrete Mathematics

Research output: Contribution to journal › Article › Academic › peer-review

4 Citations (Scopus)

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 h ≤ k servers. The problem is very poorly understood beyond uniform metrics. For this special case, the classic k-server algorithms are roughly (1 + 1/ϵ)-competitive when k = (1 + ϵ)h, for any ϵ > 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 Ω(h) irrespective of the value of k, even for depth-2 HSTs. Similarly, the Work Function Algorithm, which is believed to be optimal for all metric spaces when k = h, has competitive ratio Ω(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 + ϵ)h for any ϵ > 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.

Original language	English
Article number	28
Number of pages	26
Journal	ACM Transactions on Algorithms
Volume	15
Issue number	2
DOIs	https://doi.org/10.1145/3301314
Publication status	Published - 1 Feb 2019

Funding

A preliminary version of this article appeared in the Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2017. This work was carried out while Marek Eliáš and Grigorios Koumoutsos were PhD students at TU Eindhoven and Łukasz Jeż was postdoctoral fellow at TU Eindhoven. The first author was supported by NWO Vidi Grant No. 639.022.211 and ERC consolidator Grant No. 617951. The second author was supported by NWO Vidi Grant No. 639.022.211. The third author was supported by NWO Vidi Grant No. 639.022.211 and Polish National Science Centre Grant No. 2016/22/E/ST6/00499, 2017-2022. The last author was supported by ERC consolidator Grant No. 617951. Authors’ addresses: N. Bansal, CWI and TU Eindhoven, P.O. Box 94079, The Netherlands; email: [email protected]; M. Eliáš, EPFL, School of Computer and Communication Sciences, Building INJ (INJ132), Station 14, CH-1015, Lausanne, Switzerland; email: [email protected]; Ł. Jeż, University of Wrocław, Institute of Computer Science, ul. Joliot-Curie 15, 50-383, Wrocław, Poland; email: [email protected]; G. Koumoutsos, Université Libre de Bruxelles, Département d’Informatique, ULB CP 212, Bvd. du Triomphe, Brussels, 1050, Belgium; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2019 Association for Computing Machinery. 1549-6325/2019/02-ART28 $15.00 https://doi.org/10.1145/3301314

Keywords

Competitive analysis
K-server problem
Online algorithms
Resource augmentation

Access to Document

10.1145/3301314

Cite this

@article{9d96b694fc994026ad422204f88ded3e,

title = "The (H, k)-server problem on bounded depth trees",

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 h ≤ k servers. The problem is very poorly understood beyond uniform metrics. For this special case, the classic k-server algorithms are roughly (1 + 1/ϵ)-competitive when k = (1 + ϵ)h, for any ϵ > 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 Ω(h) irrespective of the value of k, even for depth-2 HSTs. Similarly, the Work Function Algorithm, which is believed to be optimal for all metric spaces when k = h, has competitive ratio Ω(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 + ϵ)h for any ϵ > 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.",

keywords = "Competitive analysis, K-server problem, Online algorithms, Resource augmentation",

author = "Nikhil Bansal and Marek Eli{\'a}{\v s} and {\L}ukasz Je{\.z} and Grigorios Koumoutsos",

year = "2019",

month = feb,

day = "1",

doi = "10.1145/3301314",

language = "English",

volume = "15",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery, Inc",

number = "2",

}

TY - JOUR

T1 - The (H, k)-server problem on bounded depth trees

AU - Bansal, Nikhil

AU - Eliáš, Marek

AU - Jeż, Łukasz

AU - Koumoutsos, Grigorios

PY - 2019/2/1

Y1 - 2019/2/1

N2 - 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 h ≤ k servers. The problem is very poorly understood beyond uniform metrics. For this special case, the classic k-server algorithms are roughly (1 + 1/ϵ)-competitive when k = (1 + ϵ)h, for any ϵ > 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 Ω(h) irrespective of the value of k, even for depth-2 HSTs. Similarly, the Work Function Algorithm, which is believed to be optimal for all metric spaces when k = h, has competitive ratio Ω(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 + ϵ)h for any ϵ > 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.

AB - 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 h ≤ k servers. The problem is very poorly understood beyond uniform metrics. For this special case, the classic k-server algorithms are roughly (1 + 1/ϵ)-competitive when k = (1 + ϵ)h, for any ϵ > 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 Ω(h) irrespective of the value of k, even for depth-2 HSTs. Similarly, the Work Function Algorithm, which is believed to be optimal for all metric spaces when k = h, has competitive ratio Ω(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 + ϵ)h for any ϵ > 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.

KW - Competitive analysis

KW - K-server problem

KW - Online algorithms

KW - Resource augmentation

UR - http://www.scopus.com/inward/record.url?scp=85062348462&partnerID=8YFLogxK

U2 - 10.1145/3301314

DO - 10.1145/3301314

M3 - Article

AN - SCOPUS:85062348462

SN - 1549-6325

VL - 15

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 2

M1 - 28

ER -

The (H, k)-server problem on bounded depth trees

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this