Metrical service systems with transformations

Conference item

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 T-MSS, an algorithm maintains a point in a metric space and has to serve a sequence of requests. Each request is a map (transformation) 𝑓_𝑡 : 𝐴_𝑡 → 𝐵_𝑡 between subsets 𝐴_𝑡 and 𝐵_𝑡 of the metric space. To serve it, the algorithm has to go to a point 𝑎_𝑡 ∈ 𝐴_𝑡 , paying the distance from its previous position. Then, the transformation is applied, modifying the algorithm’s state to 𝑓_𝑡 (𝑎_𝑡 ). 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 𝑘-taxi problem.

We show that for 𝛼-Lipschitz transformations, the competitive ratio is Θ(𝛼)^𝑛−2 on 𝑛-point metrics. Here, the upper bound is achieved by a deterministic algorithm and the lower bound holds even for randomized algorithms. For the 𝑘-taxi problem, we prove a competitive ratio of Õ((𝑛 log 𝑘)²). For chasing convex bodies, we show that even with contracting transformations no competitive algorithm exists.

The problem T-MSS 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.

Authors: Bubeck, S; Buchbinder, N; Coester, C; Sellke, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Host title: Leibniz International Proceedings in Informatics (LIPIcs)
• Volume: 185
• Pages: 21:1–21:20
• Article number: 21
• Place of publication: Dagstuhl, Germany
• Publication date: 2021-02-04
• Acceptance date: 2020-11-03
• Event title: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
• Event location: Online
• Event website: http://itcs-conf.org/itcs21/itcs21-cfp.html
• Event start date: 2021-01-06
• Event end date: 2021-01-08
• DOI: 10.4230/LIPIcs.ITCS.2021.21
• ISSN: 1868-8969
• ISBN: 9783959771771
• Language: English
• Keywords: 𝑘-taxi; competitive analysis; FFR; online algorithms; metrical task systems
• Subjects: Theory of computation – online algorithms