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

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

Research output: Contribution to journalArticleAcademicpeer-review

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 languageEnglish
Article number28
Number of pages26
JournalACM Transactions on Algorithms
Volume15
Issue number2
DOIs
Publication statusPublished - 1 Feb 2019

Fingerprint

Server
Competitive Ratio
Online Algorithms
Metric
Resource Augmentation
K-tree
Deterministic Algorithm
Metric space
Coverage
Optimal Solution
Lower bound

Keywords

  • Competitive analysis
  • K-server problem
  • Online algorithms
  • Resource augmentation

Cite this

Bansal, Nikhil ; Eliáš, Marek ; Jeż, Łukasz ; Koumoutsos, Grigorios. / The (H, k)-server problem on bounded depth trees. In: ACM Transactions on Algorithms. 2019 ; Vol. 15, No. 2.
@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}š and Łukasz Jeż and Grigorios Koumoutsos",
year = "2019",
month = "2",
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",

}

The (H, k)-server problem on bounded depth trees. / Bansal, Nikhil; Eliáš, Marek; Jeż, Łukasz; Koumoutsos, Grigorios.

In: ACM Transactions on Algorithms, Vol. 15, No. 2, 28, 01.02.2019.

Research output: Contribution to journalArticleAcademicpeer-review

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

VL - 15

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 2

M1 - 28

ER -