Online Metric TSP
Christian Bertram · 2025
Read Online Metric TSP by Christian Bertram (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-17716.txt.
Introduction
Christian Bertram studies a routing puzzle that unfolds one step at a time. Points of a metric space arrive one by one. Each point must be placed at once, for good, into an empty cell of an array. The cost is the sum of gaps between points that end up next to each other, and the goal is to keep that sum low.
Earlier work solved special spaces, such as lines, grids, and the uniform case. Bertram gives a method for any metric space at all. Its cost stays within a square root factor of the best plan made with full knowledge. He also shows a limit: no method can match the best known rates for both the general and uniform cases at once.
Catalog record
| CREATOR | Christian Bertram |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-17716
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Online Metric TSP Christian Bertram Abstract In the online metric traveling salesperson problem , n n points of a metric space arrive one by one and have to be placed (immediately and irrevocably) into empty cells of a size- n n array. The goal is to minimize the sum of distances between consecutive points in the array. This problem was introduced by Abrahamsen, Bercea, Beretta, Klausen, and Kozma [ESA’24] as a generalization of the online sorting problem , which was introduced by Aamand, Abrahamsen, Beretta, and Kleist [SODA’23] as a tool in their study of online geometric packing problems. Online metric TSP has been studied for a range of fixed metric spaces. For 1-dimensional Euclidean space, the problem is equivalent to online sorting, where an optimal competitive ratio of Θ ( n ) \Theta(\sqrt{n}) is known. For d d -dimensional Euclidean space, the best-known upper bound is O ( 2 d d n log n ) O(2^{d}\sqrt{dn\log n}) , leaving a gap to the Ω ( n ) \Omega(\sqrt{n}) lower bound. Finally, for the uniform metric, where all distances are 0 or 1, the optimal competitive ratio is known to be Θ ( log n ) \Theta(\log n) . We study the problem for a general metric space, presenting an algorithm with competitive ratio O ( n ) O(\sqrt{n}) . In particular, we close the gap for d d -dimensional Euclidean space, completely removing the dependence on dimension. One might hope to simultaneously guarantee competitive ratio O ( n ) O(\sqrt{n}) in general and O ( log n ) O(\log n) for the uniform metric, but we show that this is impossible. 1 Introduction 1.1 Problem definition The online metric traveling salesperson problem (online metric TSP), recently introduced by Abrahamsen, Bercea, Beretta, Klausen, and Kozma [ 2 ] , is as follows. Given a sequence x_{1},\ldots,x_{n} of points arriving one by one (with repetitions allowed) from a metric space (M,d) , assign them bijectively to array cells A[1],\ldots,A[n] . The goal is to minimize \sum_{i=1}^{n-1}d(A[i],A[i+1]) , which represents the length of the walk A[1],\ldots,A[n] . The problem is online in the sense that after receiving x_{i} , we must immediately and irrevocably set A[j]=x_{i} for some previously unused array index j , without knowledge of x_{k} for k>i . We can think of this as a metric traveling salesperson problem, where n cities are sequentially revealed, one by one, and must be placed on a unique date in the salesperson’s n -day calendar. The cost to be minimized is the length of the final n -day trip. In [ 2 ] , the metric space is fixed as 1-dimensional Euclidean space, d -dimensional Euclidean space, or a space with uniform/discrete metric (where all distances are 0 or 1). In this paper, we study the problem for a general metric space, allowing the algorithm to query the distance d(x_{i},x_{j}) between x_{i} and x_{j} , if it has received x_{i} and x_{j} . Alternatively, the i th input can be assumed to be the vector (d(x_{i},x_{1}),d(x_{i},x_{2}),\ldots,d(x_{i},x_{i-1})) . The term “online TSP” has also been used for a different, older problem where a salesperson moves through the metric space at unit speed as cities are revealed [ 3 ] . In contrast, our problem consists of constructing a fixed travel plan through irrevocable online decisions. 1.2 Prior work In [ 1 ] , the online sorting problem is introduced as part of their study of various geometric translational packing problems. The online sorting problem is equivalent to online (metric) TSP in the Euclidean unit interval [0,1] . They further essentially assume that the points 0 and 1 always show up in the input, which simplifies the analysis, as the optimal offline cost becomes 1. They present a deterministic algorithm with competitive ratio O(\sqrt{n}) for online sorting (where competitive ratio is the worst-case ratio between the algorithm’s cost and the optimal offline cost), and show an \Omega(\sqrt{n}) lower bound for deterministic algorithms. In [ 2 ] , the online sorting algorithm from [ 1 ] is generalized to points from the real line \mathbb{R} , not necessarily including 0 and 1, by employing a careful doubling technique . They maintain the O(\sqrt{n}) competitive ratio, and generalize the \Omega(\sqrt{n}) lower bound to randomized algorithms. In [ 2 ] , they further generalize the problem to online metric TSP, and consider this problem for a few fixed metric spaces. For d -dimensional Euclidean space, they present an O(2^{d}\sqrt{dn\log n}) competitive ratio algorithm, leaving a gap to their \Omega(\sqrt{n}) lower bound. For use as a subroutine in this algorithm, they consider online TSP in the uniform metric, i.e. the metric where all distances are 0 or 1. They argue that this problem has interest in its own right, corresponding to minimizing the number of task switches in scheduling, and present a tight \Theta(\log n) bound on the competitive ratio. Finally, they ask, as an open question, whether O(\sqrt{n}) is the optimal competitive ratio for arbitrary metrics. 1.3 Our results Our main result is an optimal algorithm for online metric TSP in a general metric space, settling a question posed in [ 2 ] . Theorem 1 . There exists a deterministic algorithm for online metric TSP with competitive ratio O(\sqrt{n}) . This is optimal by the \Omega(\sqrt{n}) lower bound for the Euclidean unit interval [ 1 ] , which holds even for randomized algorithms [ 2 ] . As a direct corollary, we get an optimal algorithm for online TSP in d -dimensional Euclidean space, improving upon the best-known O(2^{d}\sqrt{dn\log n}) competitive ratio algorithm [ 2 ] , completely removing the dependence on dimension. Corollary 2 . There exists a deterministic algorithm for online TSP in d -dimensional Euclidean space with competitive ratio O(\sqrt{n}) . Note, though, that the O(\sqrt{n}) bound of Theorem 1 does not match the known \Theta(\log n) bound for online TSP with uniform metric [ 2 ] . One might hope for an even stronger algorithm, obtaining an asymptotically optimal competitive ratio for every fixed metric space. We show that no such algorithm exists, hinting that our algorithm is the best one can hope for. Theorem 3 . No randomized algorithm for online metric TSP obtains both O(\log n) expected competitive ratio for the uniform metric and O(\sqrt{n}) expected competitive ratio in general. 1.4 Structure of the paper In Section 2 , we recall relevant definitions and fix notation. In Section 3 , we present our algorithm, proving Theorems 1 and 2 . In Section 4 , we confirm the worst-case optimality of our algorithm via known lower bounds, and then we show that no algorithm is simultaneously optimal for every fixed metric, proving Theorem 3 . 2 Preliminaries We will often let (M,d) be a metric space, where M is the set of points, and d\colon M\times M\to\mathbb{R}_{\geq 0} is the metric. Our main examples are d -dimensional Euclidean space and the uniform metric. The uniform metric is defined by d(x,y)=1 for all x\neq y . This is also known as the discrete metric , but we adopt the former term for consistency with [ 2 ] . Any