Metraipolis › archive › dc_5aa570fa45d9
Online Metric TSP: Beyond the $\sqrt{n}$ Barrier — arXiv:2608.07369
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.07369
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-23T15:11:04.401Z
- SHA-256 of the archived text
79f8d45bd8ce18d9fa74c490d9123f16de56150c4fa24adf6a8d8a74e9045537- Stable URL of this page
https://metraipolis.com/documento/dc_5aa570fa45d9
How to cite
Online Metric TSP: Beyond the $\sqrt{n}$ Barrier — arXiv:2608.07369 — arXiv (en), https://arxiv.org/abs/2608.07369 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5aa570fa45d9 (Metraipolis archive dc_5aa570fa45d9, sha256 79f8d45bd8ce18d9fa74c490d9123f16de56150c4fa24adf6a8d8a74e9045537)
BibTeX
@misc{dc5aa570fa45d9,
title = {Online Metric TSP: Beyond the $sqrtn$ Barrier — arXiv:2608.07369},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.07369},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5aa570fa45d9; sha256 79f8d45bd8ce18d9fa74c490d9123f16de56150c4fa24adf6a8d8a74e9045537},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.07369. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 \ge 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^{n}$, 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 [ESA 2025] recently showed that the competitive ratio is $\Theta(\sqrt{n})$. We investigate the tradeoff between space usage and competitiveness between these extremes. We note that this tradeoff was previously explored by the authors [SODA 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+\epsilon) n$ space that achieves a competitive ratio of $O(\log^{3} n / \epsilon)$, for any $\epsilon \le 1$. In particular, increasing the space from $n$ to $2n$ improves the competitive ratio from $\Theta(\sqrt{n})$ to $O(\log^{3} n)$. We complement this with a lower bound showing that for $m = n^{1+\epsilon}$, any deterministic algorithm has a competitive ratio $\Omega(1/\epsilon)$, for all $\epsilon \ge \Omega(\log \log n / \log n)$. Consequently, even with $m = O(n \cdot \mathrm{polylog}(n))$, deterministic algorithms cannot achieve a constant competitive ratio.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-10 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.07369 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-23T15:08:55.962Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).