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.
The (h,k)-server problem on bounded depth trees
Eliáš, Marek
;
2019-01-01
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.File | Dimensione | Formato | |
---|---|---|---|
1608.08527.pdf
accesso aperto
Tipologia:
Documento in Pre-print (Pre-print document)
Licenza:
Creative commons
Dimensione
397.88 kB
Formato
Adobe PDF
|
397.88 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.