We study the Double Coverage (DC) algorithm for the k-server problem in tree metrics in the (h, k)-setting, i.e., when DC with k servers is compared against an offline optimum algorithm with h ≤ k servers. It is well-known that in such metric spaces DC is k-competitive (and thus optimal) for h = k. We prove that even if k > h the competitive ratio of DC does not improve; in fact, it increases slightly as k grows, tending to h + 1. Specifically, we give matching upper and lower bounds of (ℎ+1)/(+1) on the competitive ratio of DC on any tree metric.

Tight bounds for Double Coverage against weak adversaries

Eliáš, Marek
;
2018

Abstract

We study the Double Coverage (DC) algorithm for the k-server problem in tree metrics in the (h, k)-setting, i.e., when DC with k servers is compared against an offline optimum algorithm with h ≤ k servers. It is well-known that in such metric spaces DC is k-competitive (and thus optimal) for h = k. We prove that even if k > h the competitive ratio of DC does not improve; in fact, it increases slightly as k grows, tending to h + 1. Specifically, we give matching upper and lower bounds of (ℎ+1)/(+1) on the competitive ratio of DC on any tree metric.
2018
2016
Bansal, Nikhil; Eliáš, Marek; Jeż, Łukasz; Koumoutsos, Grigorios; Pruhs, Kirk
File in questo prodotto:
File Dimensione Formato  
2015-DC_weak_adversaries-jour.pdf

accesso aperto

Descrizione: Main article
Tipologia: Documento in Pre-print (Pre-print document)
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 229.54 kB
Formato Adobe PDF
229.54 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11565/4044267
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
social impact