Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'487'895
Articles rated: 2609

28 March 2024
 
  » arxiv » 1608.8527

 Article overview


New Bounds for the $(h,k)$-Server Problem
Nikhil Bansal ; Marek Eliáš ; Łukasz Jeż ; Grigorios Koumoutsos ;
Date 30 Aug 2016
AbstractWe 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   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  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






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica