Abstract
In this paper, we study the weighted kserver problem on the uniform metric in both the offline and online settings. We start with the offline setting. In contrast to the (unweighted) kserver problem which has a polynomialtime solution using mincost flows, there are strong computational lower bounds for the weighted kserver problem, even on the uniform metric. Specifically, we show that assuming the unique games conjecture, there are no polynomialtime algorithms with a subpolynomial approximation factor, even if we use cresource 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 constantapproximation 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 kserver 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 twostage approach of first obtaining a fractional solution using the online primaldual 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 kServer Problem}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {12:112:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772969},
ISSN = {18688969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18837},
URN = {urn:nbn:de:0030drops188375},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.12},
annote = {Keywords: Online Algorithms, Weighted kserver, Integrality Gap, Hardness}
}
Keywords: 

Online Algorithms, Weighted kserver, Integrality Gap, Hardness 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) 
Issue Date: 

2023 
Date of publication: 

04.09.2023 