---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Jannik
      foaf_name: Castenow, Jannik
      foaf_surname: Castenow
      foaf_workInfoHomepage: http://www.librecat.org/personId=38705
  - foaf_Person:
      foaf_givenName: Björn
      foaf_name: Feldkord, Björn
      foaf_surname: Feldkord
      foaf_workInfoHomepage: http://www.librecat.org/personId=22704
  - foaf_Person:
      foaf_givenName: Till
      foaf_name: Knollmann, Till
      foaf_surname: Knollmann
      foaf_workInfoHomepage: http://www.librecat.org/personId=39241
    orcid: 0000-0003-2014-4696
  - foaf_Person:
      foaf_givenName: Manuel
      foaf_name: Malatyali, Manuel
      foaf_surname: Malatyali
      foaf_workInfoHomepage: http://www.librecat.org/personId=41265
  - foaf_Person:
      foaf_givenName: Friedhelm
      foaf_name: Meyer auf der Heide, Friedhelm
      foaf_surname: Meyer auf der Heide
      foaf_workInfoHomepage: http://www.librecat.org/personId=15523
  bibo_doi: 10.1145/3490148.3538595
  dct_date: 2022^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/9781450391467
  dct_language: eng
  dct_publisher: Association for Computing Machinery@
  dct_subject:
  - K-Server Problem
  - Heterogeneity
  - Online Caching
  dct_title: The k-Server with Preferences Problem@
...