Deterministic generalized k-server: tower lower bound and strict upper bound

Source: github.com/marek-elias/generalized-k-server-lean/tree/a0ef2…

Andrea Celli, Jeffrey Theodore Rigos Champion, Valerio Cini, Nemanja Draganic, Marek Elias, Mariana Botelho da Gama, Paul Lou, Giulio Malavolta, Emmanuela Orsini, Adam Polak, Mariana Rio Costa, Laura Sanita, Jonas Benjamin Schmidt

Palomar Registrypalomar/PALOMAR-2026-11-03-000023Nov 3, 2026cs.DSscore 0

For generalized k-server, each named server moves in its own metric space, a request specifies one point per space, and matching any coordinate serves the request. The development proves a height-k tower lower bound on the deterministic competitive ratio on k real lines for k at least three, allowing arbitrary additive constants. It also proves existence of a lazy deterministic algorithm on arbitrary metric spaces with arbitrary positive movement weights and prescribed initial configuration, with an explicit factor depending only on k and no additive cost or horizon input. The refined…

RepositoryJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/palomar/PALOMAR-2026-11-03-000023
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-03-000023/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-03-000023/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'