2026-09-08T02:22:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26407 2026-09-05T19:42:22Z ddc:004 open_access

Online Metric TSP: Beyond the √n Barrier Azar, Yossi Panigrahi, Debmalya Vardi, Or Online algorithms competitive analysis metric TSP space-competitiveness tradeoff routing problems We study an online variant of the Traveling Salesperson Problem (TSP) in which n points arrive sequentially and must be inserted into an evolving tour. In the classical setting where arbitrary insertions are allowed, an O(log n)-competitive algorithm has been known since the 1970s (Rosenkrantz, Stearns and Lewis 1977, Imase and Waxman 1991). Recently, Abrahamsen, Bercea, Beretta, Klausen, and Kozma [ESA 2024] introduced online metric TSP, a stricter model in which each arriving point must be assigned to a distinct cell of an array of size m ≥ n, with the final tour order induced by the non-empty cells; the parameter m captures the space usage of the algorithm. When m = 2ⁿ, this model recovers arbitrary insertions and therefore admits an O(log n)-competitive algorithm. In contrast, when m = n, i.e., when each point’s position is fixed on arrival, Bertram [Christian Bertram, 2025] recently showed that the competitive ratio is Θ(√n). We investigate the tradeoff between space usage and competitiveness between these extremes. We note that this tradeoff was previously explored by the authors in [Yossi Azar et al., 2026] for the online sorting problem, which is the special case of online metric TSP on a line metric. Our main result is a deterministic online metric TSP algorithm using m = (1+ε) n space that achieves a competitive ratio of O(log³ n/ε), for any ε ≤ 1. In particular, increasing the space from n to 2n improves the competitive ratio from Θ(√n) to O(log³ n). We complement this with a lower bound showing that for m = n^{1+ε}, any deterministic algorithm has a competitive ratio Ω(1/ε), for all ε ≥ Ω(log log n / log n). Consequently, even with m = O(n ⋅ polylog(n)), deterministic algorithms cannot achieve a constant competitive ratio. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yossi Azar and Debmalya Panigrahi and Or Vardi 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.18 urn:nbn:de:0030-drops-264071 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.18 eng https://creativecommons.org/licenses/by/4.0/legalcode