|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Competitive Algorithms for Generalized k-Server in Uniform Metrics | | Nikhil Bansal
; Marek Elias
; Grigorios Koumoutsos
; Jesper Nederlof
; | | Date: |
14 Jul 2017 | | Abstract: | The generalized k-server problem is a far-reaching extension of the k-server
problem with several applications. Here, each server $s_i$ lies in its own
metric space $M_i$. A request is a k-tuple $r = (r_1,r_2,dotsc,r_k)$ and to
serve it, we need to move some server $s_i$ to the point $r_i in M_i$, 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 $O(k 2^k)$ and
$O(k^3 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 $2^k-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. | | Source: | arXiv, 1707.4519 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER