---
_id: '31847'
abstract:
- lang: eng
text: "The famous $k$-Server Problem covers plenty of resource allocation scenarios,
and several variations have been studied extensively for decades. However, to
the best of our knowledge, no research has considered the problem if the servers
are not identical and requests can express which specific servers should serve
them. Therefore, we present a new model generalizing the $k$-Server Problem by
*preferences* of the requests and proceed to study it in a uniform metric space
for deterministic online algorithms (the special case of paging).\r\n\r\nIn our
model, requests can either demand to be answered by any server (*general requests*)
or by a specific one (*specific requests*). If only general requests appear, the
instance is one of the original $k$-Server Problem, and a lower bound for the
competitive ratio of $k$ applies. If only specific requests appear, a solution
with a competitive ratio of $1$ becomes trivial since there is no freedom regarding
the servers' movements. Perhaps counter-intuitively, we show that if both kinds
of requests appear, the lower bound raises to $2k-1$.\r\n\r\nWe study deterministic
online algorithms in uniform metrics and present two algorithms. The first one
has an adaptive competitive ratio dependent on the frequency of specific requests.
It achieves a worst-case competitive ratio of $3k-2$ while it is optimal when
only general or only specific requests appear (competitive ratio of $k$ and $1$,
respectively). The second has a fixed close-to-optimal worst-case competitive
ratio of $2k+14$. For the first algorithm, we show a lower bound of $3k-2$, while
the second algorithm has a lower bound of $2k-1$ when only general requests appear.\r\n
\ \r\nThe two algorithms differ in only one behavioral rule for each server
that significantly influences the competitive ratio. Each server acting according
to the rule allows approaching the worst-case lower bound, while it implies an
increased lower bound for $k$-Server instances. In other words, there is a trade-off
between performing well against instances of the $k$-Server Problem and instances
containing specific requests. We also show that no deterministic online algorithm
can be optimal for both kinds of instances simultaneously."
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Manuel
full_name: Malatyali, Manuel
id: '41265'
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Castenow J, Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. The
k-Server with Preferences Problem. In: Proceedings of the 34th ACM Symposium
on Parallelism in Algorithms and Architectures. Association for Computing
Machinery; 2022:345-356. doi:10.1145/3490148.3538595'
apa: Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., & Meyer auf der
Heide, F. (2022). The k-Server with Preferences Problem. Proceedings of the
34th ACM Symposium on Parallelism in Algorithms and Architectures, 345–356.
https://doi.org/10.1145/3490148.3538595
bibtex: '@inproceedings{Castenow_Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2022,
title={The k-Server with Preferences Problem}, DOI={10.1145/3490148.3538595},
booktitle={Proceedings of the 34th ACM Symposium on Parallelism in Algorithms
and Architectures}, publisher={Association for Computing Machinery}, author={Castenow,
Jannik and Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer
auf der Heide, Friedhelm}, year={2022}, pages={345–356} }'
chicago: Castenow, Jannik, Björn Feldkord, Till Knollmann, Manuel Malatyali, and
Friedhelm Meyer auf der Heide. “The K-Server with Preferences Problem.” In Proceedings
of the 34th ACM Symposium on Parallelism in Algorithms and Architectures,
345–56. Association for Computing Machinery, 2022. https://doi.org/10.1145/3490148.3538595.
ieee: 'J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der
Heide, “The k-Server with Preferences Problem,” in Proceedings of the 34th
ACM Symposium on Parallelism in Algorithms and Architectures, 2022, pp. 345–356,
doi: 10.1145/3490148.3538595.'
mla: Castenow, Jannik, et al. “The K-Server with Preferences Problem.” Proceedings
of the 34th ACM Symposium on Parallelism in Algorithms and Architectures,
Association for Computing Machinery, 2022, pp. 345–56, doi:10.1145/3490148.3538595.
short: 'J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide,
in: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures,
Association for Computing Machinery, 2022, pp. 345–356.'
date_created: 2022-06-10T09:06:42Z
date_updated: 2022-08-02T08:07:30Z
department:
- _id: '63'
doi: 10.1145/3490148.3538595
external_id:
arxiv:
- '2205.11102'
keyword:
- K-Server Problem
- Heterogeneity
- Online Caching
language:
- iso: eng
page: 345-356
project:
- _id: '1'
name: 'SFB 901: SFB 901'
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '5'
name: 'SFB 901 - A1: SFB 901 - Subproject A1'
publication: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and
Architectures
publication_identifier:
isbn:
- '9781450391467'
publisher: Association for Computing Machinery
status: public
title: The k-Server with Preferences Problem
type: conference
user_id: '39241'
year: '2022'
...