| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
New Bounds for the $(h,k)$-Server Problem | Nikhil Bansal
; Marek Eliáš
; Łukasz Jeż
; Grigorios Koumoutsos
; | Date: |
30 Aug 2016 | 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 leq k$ 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. | Source: | arXiv, 1608.8527 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |