License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.14
URN: urn:nbn:de:0030-drops-115104
Go to the corresponding LIPIcs Volume Portal

Bienkowski, Marcin ; Jez, Lukasz ; Schmidt, Pawel

Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics

LIPIcs-ISAAC-2019-14.pdf (0.5 MB)


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.

BibTeX - Entry

  author =	{Marcin Bienkowski and Lukasz Jez and Pawel Schmidt},
  title =	{{Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Pinyan Lu and Guochuan Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-115104},
  doi =		{10.4230/LIPIcs.ISAAC.2019.14},
  annote =	{Keywords: k-server, generalized k-server, competitive analysis}

Keywords: k-server, generalized k-server, competitive analysis
Collection: 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Issue Date: 2019
Date of publication: 28.11.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI