The generalized k-server problem is a far-reaching extension of the k-server problem with several applications. Here, each server si lies in its own metric space Mi. A request is a k-tuple r = (r1, r2, … , rk), which is served by moving some server si to the point ri ∈ Mi, and the goal is to minimize the total distance traveled by the servers. Despite much work, no f(k)-competitive algorithm is known for the problem for k > 2 servers, even for special cases such as uniform metrics and lines. Here, we consider the problem in uniform metrics and give the first f(k)-competitive algorithms for general k. In particular, we obtain deterministic and randomized algorithms with competitive ratio k · 2k and O(k3log k) respectively. Our deterministic bound is based on a novel application of the polynomial method to online algorithms, and essentially matches the long-known lower bound of 2k − 1. We also give a (2^{2^{O(k)}} ) -competitive deterministic algorithm for weighted uniform metrics, which also essentially matches the recent doubly exponential lower bound for the problem.

Competitive algorithms for generalized k-server in uniform metrics

Elias, Marek
;
In corso di stampa

Abstract

The generalized k-server problem is a far-reaching extension of the k-server problem with several applications. Here, each server si lies in its own metric space Mi. A request is a k-tuple r = (r1, r2, … , rk), which is served by moving some server si to the point ri ∈ Mi, and the goal is to minimize the total distance traveled by the servers. Despite much work, no f(k)-competitive algorithm is known for the problem for k > 2 servers, even for special cases such as uniform metrics and lines. Here, we consider the problem in uniform metrics and give the first f(k)-competitive algorithms for general k. In particular, we obtain deterministic and randomized algorithms with competitive ratio k · 2k and O(k3log k) respectively. Our deterministic bound is based on a novel application of the polynomial method to online algorithms, and essentially matches the long-known lower bound of 2k − 1. We also give a (2^{2^{O(k)}} ) -competitive deterministic algorithm for weighted uniform metrics, which also essentially matches the recent doubly exponential lower bound for the problem.
2022
Bansal, Nikhil; Elias, Marek; Koumoutsos, Grigorios; Nederlof, Jesper
File in questo prodotto:
File Dimensione Formato  
articleACM.pdf

accesso aperto

Descrizione: article
Tipologia: Pdf editoriale (Publisher's layout)
Licenza: Non specificato
Dimensione 555.54 kB
Formato Adobe PDF
555.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/4053345
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact