
Open access
Date
2020-12Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
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. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000452264Publication status
publishedExternal links
Book title
31st International Symposium on Algorithms and Computation (ISAAC 2020)Journal / series
Leibniz International Proceedings in Informatics (LIPIcs)Volume
Pages / Article No.
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für InformatikEvent
Subject
Online k-Server; Paging; Delayed Service; Conservative AlgorithmsOrganisational unit
03604 - Wattenhofer, Roger / Wattenhofer, Roger
More
Show all metadata
ETH Bibliography
yes
Altmetrics