Metrical Service Systems with Transformations
summary
Defines Metrical Server Systems with Transformations: each request is a map from domain AT to image BT and the algorithm pays only to move into AT. Shows any finite metric admits a finite extension M̂ that extends partial isometries, so TMSS with isometries reduces to classic MSS on M̂ and yields polylog competitive ratios in |M̂|. Gives a K‑taxi algorithm polynomial in |M| and log K (after tree embedding). Exhibits an infinite lower bound for contracting maps on infinite spaces, and for n‑point spaces proves deterministic bounds roughly α^n (or 6^n) via ultrametric and symmetric tree constructions that lose factors like (α+1)^{n‑2} and 2^{n‑1}.
AI-written summary · about