### 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 | |

Publication status | Published - 1 Feb 2019 |

### Fingerprint

### Keywords

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

### Cite this

*ACM Transactions on Algorithms*,

*15*(2), [28]. https://doi.org/10.1145/3301314

}

*ACM Transactions on Algorithms*, vol. 15, no. 2, 28. https://doi.org/10.1145/3301314

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

Research output: Contribution to journal › Article › Academic › peer-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 -