{"id":"palomar/PALOMAR-2026-11-03-000023","url":"https://github.com/marek-elias/generalized-k-server-lean/tree/a0ef235a4cc8e1f1e695f0440f0a9dc369e3c804/formalization","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-03-000023-v1.json","repo":"https://github.com/marek-elias/generalized-k-server-lean","tags":["cs.DS","msc:68W27","msc:68W40","msc:03B35"],"score":0,"title":"Deterministic generalized k-server: tower lower bound and strict upper bound","trust":"high","domain":"cs.DS","source":"palomar","authors":["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"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"verified":true,"discussed":0,"published":"2026-11-03","reactions":{},"formalized":true,"formalizes":[{"title":"Generalized k-server: problem and theorem statements","identifier":"","relationship":"formalizes"},{"title":"A Tower Lower Bound for Generalized k-Server: Multi-scale helpers on the line","identifier":"","relationship":"formalizes"},{"title":"Generalized k-server on arbitrary metrics","identifier":"","relationship":"formalizes"},{"title":"Removing the log* k loss in tower height","identifier":"","relationship":"formalizes"}]}