Competitive algorithms for generalized k-server in uniform metrics.

N. Bansal, M. Elias, G. Koumoutsos, J. Nederlof

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)
69 Downloads (Pure)

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 ktuple r = (r1; r2; : : : ; rk) and to serve it, we need to move 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 > ϵ 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(k3 log 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 22O(k) -competitive deterministic algorithm for weighted uniform metrics, which also essentially matches the recent doubly exponential lower bound for the problem.

Original languageEnglish
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
Place of Publications.l.
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages992-1001
Number of pages10
ISBN (Electronic)978-1-61197-503-1
DOIs
Publication statusPublished - 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018) - Astor Crowne Plaza, New Orleans, United States
Duration: 7 Jan 201810 Jan 2018
Conference number: 29
https://www.siam.org/meetings/da18/

Conference

Conference29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)
Abbreviated titleSODA 2018
CountryUnited States
CityNew Orleans
Period7/01/1810/01/18
Internet address

Fingerprint Dive into the research topics of 'Competitive algorithms for generalized k-server in uniform metrics.'. Together they form a unique fingerprint.

Cite this