DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2020.61

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

Authors: Predrag Krnetić, Darya Melnyk, Yuyi Wang, and Roger Wattenhofer

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

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.

Cite as

Predrag Krnetić, Darya Melnyk, Yuyi Wang, and Roger Wattenhofer. The k-Server Problem with Delays on the Uniform Metric Space. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 61:1-61:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{krnetic_et_al:LIPIcs.ISAAC.2020.61,
  author =	{Krneti\'{c}, Predrag and Melnyk, Darya and Wang, Yuyi and Wattenhofer, Roger},
  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 =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.61},
  URN =		{urn:nbn:de:0030-drops-134056},
  doi =		{10.4230/LIPIcs.ISAAC.2020.61},
  annote =	{Keywords: Online k-Server, Paging, Delayed Service, Conservative Algorithms}
}

Search Results

Documents authored by Krnetić, Predrag

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

Abstract

Cite as

Thanks for your feedback!

Could not send message