Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2504.17716 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911042783674368 |
|---|---|
| author | Bertram, Christian |
| author_facet | Bertram, Christian |
| contents | In the online metric traveling salesperson problem, $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$ 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 $Θ(\sqrt n)$ is known. For $d$-dimensional Euclidean space, the best-known upper bound is $O(2^{d} \sqrt{dn\log n})$, leaving a gap to the $Ω(\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)$.
We study the problem for a general metric space, presenting an algorithm with competitive ratio $O(\sqrt n)$. In particular, we close the gap for $d$-dimensional Euclidean space, completely removing the dependence on dimension. One might hope to simultaneously guarantee competitive ratio $O(\sqrt n)$ in general and $O(\log n)$ for the uniform metric, but we show that this is impossible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17716 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online Metric TSP Bertram, Christian Data Structures and Algorithms In the online metric traveling salesperson problem, $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$ 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 $Θ(\sqrt n)$ is known. For $d$-dimensional Euclidean space, the best-known upper bound is $O(2^{d} \sqrt{dn\log n})$, leaving a gap to the $Ω(\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)$. We study the problem for a general metric space, presenting an algorithm with competitive ratio $O(\sqrt n)$. In particular, we close the gap for $d$-dimensional Euclidean space, completely removing the dependence on dimension. One might hope to simultaneously guarantee competitive ratio $O(\sqrt n)$ in general and $O(\log n)$ for the uniform metric, but we show that this is impossible. |
| title | Online Metric TSP |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.17716 |