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

N. Bansal, M. Elias, L. Jez, G. Koumoutsos

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

6 Citaten (Scopus)
72 Downloads (Pure)

Samenvatting

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 O(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 O(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, and gives the strongest known lower bound for the problem on general metrics.
Originele taal-2Engels
TitelProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 16-19 January 2017, Barcelona, Spain
RedacteurenPhilip N. Klein
Plaats van producties.l.
UitgeverijSociety for Industrial and Applied Mathematics (SIAM)
Pagina's1022-1037
Aantal pagina's16
ISBN van elektronische versie978-1-61197-478-2
DOI's
StatusGepubliceerd - 2017
Evenement28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) - Barcelona, Spanje
Duur: 16 jan 201719 jan 2017
Congresnummer: 28

Congres

Congres28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)
Verkorte titelSODA 2017
Land/RegioSpanje
StadBarcelona
Periode16/01/1719/01/17

Vingerafdruk

Duik in de onderzoeksthema's van 'The (h,k)-server problem on bounded-depth trees.'. Samen vormen ze een unieke vingerafdruk.

Citeer dit