Abstract
We consider a generalization of the fundamental online metrical service systems (MSS) problem where the feasible region can be transformed between requests. In this problem, which we call TMSS, an algorithm maintains a point in a metric space and has to serve a sequence of requests. Each request is a map (transformation) f_t: A_t → B_t between subsets A_t and B_t of the metric space. To serve it, the algorithm has to go to a point a_t ∈ A_t, paying the distance from its previous position. Then, the transformation is applied, modifying the algorithm’s state to f_t(a_t). Such transformations can model, e.g., changes to the environment that are outside of an algorithm’s control, and we therefore do not charge any additional cost to the algorithm when the transformation is applied. The transformations also allow to model requests occurring in the ktaxi problem.
We show that for αLipschitz transformations, the competitive ratio is Θ(α)^{n2} on npoint metrics. Here, the upper bound is achieved by a deterministic algorithm and the lower bound holds even for randomized algorithms. For the ktaxi problem, we prove a competitive ratio of Õ((nlog k)²). For chasing convex bodies, we show that even with contracting transformations no competitive algorithm exists.
The problem TMSS has a striking connection to the following deep mathematical question: Given a finite metric space M, what is the required cardinality of an extension M̂ ⊇ M where each partial isometry on M extends to an automorphism? We give partial answers for special cases.
BibTeX  Entry
@InProceedings{bubeck_et_al:LIPIcs.ITCS.2021.21,
author = {S\'{e}bastien Bubeck and Niv Buchbinder and Christian Coester and Mark Sellke},
title = {{Metrical Service Systems with Transformations}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {21:121:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13560},
URN = {urn:nbn:de:0030drops135608},
doi = {10.4230/LIPIcs.ITCS.2021.21},
annote = {Keywords: Online algorithms, competitive analysis, metrical task systems, ktaxi}
}
Keywords: 

Online algorithms, competitive analysis, metrical task systems, ktaxi 
Collection: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021) 
Issue Date: 

2021 
Date of publication: 

04.02.2021 