License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.12
URN: urn:nbn:de:0030-drops-188375
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18837/
Go to the corresponding LIPIcs Volume Portal

Gupta, Anupam ; Kumar, Amit ; Panigrahi, Debmalya

Efficient Algorithms and Hardness Results for the Weighted k-Server Problem

pdf-format:
LIPIcs-APPROX12.pdf (0.8 MB)

Abstract

In this paper, we study the weighted k-server problem on the uniform metric in both the offline and online settings. We start with the offline setting. In contrast to the (unweighted) k-server problem which has a polynomial-time solution using min-cost flows, there are strong computational lower bounds for the weighted k-server problem, even on the uniform metric. Specifically, we show that assuming the unique games conjecture, there are no polynomial-time algorithms with a sub-polynomial approximation factor, even if we use c-resource augmentation for c < 2. Furthermore, if we consider the natural LP relaxation of the problem, then obtaining a bounded integrality gap requires us to use at least ? resource augmentation, where ? is the number of distinct server weights. We complement these results by obtaining a constant-approximation algorithm via LP rounding, with a resource augmentation of (2+ε)? for any constant ε > 0.
In the online setting, an exp(k) lower bound is known for the competitive ratio of any randomized algorithm for the weighted k-server problem on the uniform metric. In contrast, we show that 2?-resource augmentation can bring the competitive ratio down by an exponential factor to only O(?² log ?). Our online algorithm uses the two-stage approach of first obtaining a fractional solution using the online primal-dual framework, and then rounding it online.

BibTeX - Entry

@InProceedings{gupta_et_al:LIPIcs.APPROX/RANDOM.2023.12,
  author =	{Gupta, Anupam and Kumar, Amit and Panigrahi, Debmalya},
  title =	{{Efficient Algorithms and Hardness Results for the Weighted k-Server Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18837},
  URN =		{urn:nbn:de:0030-drops-188375},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.12},
  annote =	{Keywords: Online Algorithms, Weighted k-server, Integrality Gap, Hardness}
}

Keywords: Online Algorithms, Weighted k-server, Integrality Gap, Hardness
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

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