Bienkowski, Marcin
[Verfasser:in];
Jeż, Łukasz
[Verfasser:in];
Schmidt, Paweł
[Verfasser:in]
;
Marcin Bienkowski and Łukasz Jeż and Paweł Schmidt
[Mitwirkende:r]
Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
The generalized k-server problem is an extension of the weighted k-server problem, which in turn extends the classic k-server problem. In the generalized k-server problem, each of k servers s_1, ., s_k remains in its own metric space M_i. A request is a tuple (r_1,.,r_k), where r_i in M_i, and to service it, an algorithm needs to move at least one server s_i to the point r_i. The objective is to minimize the total distance traveled by all servers. In this paper, we focus on the generalized k-server problem for the case where all M_i are uniform metrics. We show an O(k^2 * log k)-competitive randomized algorithm improving over a recent result by Bansal et al. [SODA 2018], who gave an O(k^3 * log k)-competitive algorithm. To this end, we define an abstract online problem, called Hydra game, and we show that a randomized solution of low cost to this game implies a randomized algorithm to the generalized k-server problem with low competitive ratio. We also show that no randomized algorithm can achieve competitive ratio lower than Omega(k), thus improving the lower bound of Omega(k / log^2 k) by Bansal et al.