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

2 Citations (Scopus)
43 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 k-tuple 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 > 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(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 publicationProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana
Place of Publications.l.
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages992-1001
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

Servers
Polynomials

Cite this

Bansal, N., Elias, M., Koumoutsos, G., & Nederlof, J. (2018). Competitive algorithms for generalized k-server in uniform metrics. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana (pp. 992-1001). s.l.: Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611975031.64
Bansal, N. ; Elias, M. ; Koumoutsos, G. ; Nederlof, J. / Competitive algorithms for generalized k-server in uniform metrics. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana. s.l. : Society for Industrial and Applied Mathematics (SIAM), 2018. pp. 992-1001
@inproceedings{e80e35207d4748c2bac55ba786b2fa02,
title = "Competitive algorithms for generalized k-server in uniform metrics.",
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) 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 > 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(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.",
author = "N. Bansal and M. Elias and G. Koumoutsos and J. Nederlof",
year = "2018",
doi = "10.1137/1.9781611975031.64",
language = "English",
pages = "992--1001",
booktitle = "Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana",
publisher = "Society for Industrial and Applied Mathematics (SIAM)",
address = "United States",

}

Bansal, N, Elias, M, Koumoutsos, G & Nederlof, J 2018, Competitive algorithms for generalized k-server in uniform metrics. in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana. Society for Industrial and Applied Mathematics (SIAM), s.l., pp. 992-1001, 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, United States, 7/01/18. https://doi.org/10.1137/1.9781611975031.64

Competitive algorithms for generalized k-server in uniform metrics. / Bansal, N.; Elias, M.; Koumoutsos, G.; Nederlof, J.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana. s.l. : Society for Industrial and Applied Mathematics (SIAM), 2018. p. 992-1001.

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

TY - GEN

T1 - Competitive algorithms for generalized k-server in uniform metrics.

AU - Bansal, N.

AU - Elias, M.

AU - Koumoutsos, G.

AU - Nederlof, J.

PY - 2018

Y1 - 2018

N2 - 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) 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 > 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(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.

AB - 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) 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 > 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(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.

U2 - 10.1137/1.9781611975031.64

DO - 10.1137/1.9781611975031.64

M3 - Conference contribution

SP - 992

EP - 1001

BT - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana

PB - Society for Industrial and Applied Mathematics (SIAM)

CY - s.l.

ER -

Bansal N, Elias M, Koumoutsos G, Nederlof J. Competitive algorithms for generalized k-server in uniform metrics. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana. s.l.: Society for Industrial and Applied Mathematics (SIAM). 2018. p. 992-1001 https://doi.org/10.1137/1.9781611975031.64