Name
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.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.5555/3174304.3175334 | SODA '18: Symposium on Discrete Algorithms
New Orleans
Louisiana
January, 2018 |
DocType | Volume | ISBN |
Conference | abs/1707.04519 | 978-1-61197-503-1 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikhil Bansal | 1 | 3043 | 230.41 |
| Marek Eliás | 2 | 4 | 1.48 |
| Grigorios Koumoutsos | 3 | 4 | 3.17 |
| Jesper Nederlof | 4 | 294 | 24.22 |