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.2020.61
URN: urn:nbn:de:0030-drops-134056
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13405/
Go to the corresponding LIPIcs Volume Portal

Krnetić, Predrag ; Melnyk, Darya ; Wang, Yuyi ; Wattenhofer, Roger

The k-Server Problem with Delays on the Uniform Metric Space

pdf-format:
LIPIcs-ISAAC-2020-61.pdf (0.4 MB)

Abstract

In this paper, we present tight bounds for the k-server problem with delays in the uniform metric space. The problem is defined on n+k nodes in the uniform metric space which can issue requests over time. These requests can be served directly or with some delay using k servers, by moving a server to the corresponding node with an open request. The task is to find an online algorithm that can serve the requests while minimizing the total moving and delay costs. We first provide a lower bound by showing that the competitive ratio of any deterministic online algorithm cannot be better than (2k+1) in the clairvoyant setting. We will then show that conservative algorithms (without delay) can be equipped with an accumulative delay function such that all such algorithms become (2k+1)-competitive in the non-clairvoyant setting. Together, the two bounds establish a tight result for both, the clairvoyant and the non-clairvoyant settings.

BibTeX - Entry

@InProceedings{krneti_et_al:LIPIcs:2020:13405,
  author =	{Predrag Krnetić and Darya Melnyk and Yuyi Wang and Roger Wattenhofer},
  title =	{{The k-Server Problem with Delays on the Uniform Metric Space}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{61:1--61:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13405},
  URN =		{urn:nbn:de:0030-drops-134056},
  doi =		{10.4230/LIPIcs.ISAAC.2020.61},
  annote =	{Keywords: Online k-Server, Paging, Delayed Service, Conservative Algorithms}
}

Keywords: Online k-Server, Paging, Delayed Service, Conservative Algorithms
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

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