Constant-Factor Approximability of the Traveling Salesman Problem with Line Neighborhoods in $\mathbb{R}^3$

The Euclidean Traveling Salesman Problem with Neighborhoods (TSPN) asks for a shortest closed tour that intersects each of a given collection of regions. When the regions are full lines in $\mathbb{R}^3$, the best known polynomial-time approximation ratio is $O(\log^3 n)$ (Dumitrescu and Tóth, via a reduction to group Steiner tree), while the best lower bound is APX-hardness; an $O(\log^2 n)$-approximation is known only in quasi-polynomial time $n^{O(\log\log n)}$. Antoniadis, Kisfaludi-Bak, Laekhanukit, and Vaz (SWAT 2022), who established these hardness and quasi-polynomial results, posed as the most important open question whether TSPN with line neighborhoods in $\mathbb{R}^3$ admits a constant-factor polynomial-time approximation, or whether an inapproximability result rules one out. No resolution in either direction is known in the literature to date: the question, together with the paper's companion questions on polylogarithmic hardness transfer and polynomializing the quasi-polynomial algorithm, remains open.

Background

The Traveling Salesman Problem (TSP) asks for a shortest closed tour visiting a given set of points in a metric space. The Traveling Salesman Problem with Neighborhoods (TSPN), introduced in the 1990s as a generalization of Euclidean TSP, replaces each input point by a region (a 'neighborhood') and asks for a shortest closed tour that intersects every region, where the intersection point with each region may be chosen freely. TSPN models touring and data-collection tasks (a courier who must reach any point of each delivery zone, a sensor that must come within range of each target), and it captures the group Steiner tree problem — in which one seeks a cheapest subgraph connecting one terminal from each of a family of vertex subsets ('groups') — so TSPN is much harder than classical TSP. This record concerns TSPN where the neighborhoods are affine subspaces: a $k$-dimensional flat in $\mathbb{R}^d$ is a translate of a $k$-dimensional linear subspace (points for $k=0$, lines for $k=1$, hyperplanes for $k=d-1$). As regards approximation schemes the picture over flats is complete. Euclidean TSP itself has a PTAS — a polynomial-time approximation scheme, i.e., a $(1+\varepsilon)$-approximation for every fixed $\varepsilon>0$ — via Arora's randomized dynamic program over hierarchically dissected cubes. Hyperplane neighborhoods admit a PTAS, later improved to an EPTAS — a PTAS whose running time is $f(\varepsilon,d)\cdot n^{O(1)}$ — by Antoniadis, Fleszar, Hoeksma, and Schewior. Lines in the plane can even be solved exactly in $O(n^4\log n)$ time via a reduction to the shortest watchman route problem (finding a shortest closed curve inside a polygonal region that sees every point of it), with a linear-time $1.28$-approximation due to Dumitrescu. In contrast, Antoniadis, Kisfaludi-Bak, Laekhanukit, and Vaz proved that TSPN with line neighborhoods in $\mathbb{R}^d$ is APX-hard for every $d\ge 3$ — some constant ratio $\rho>1$ is unreachable in polynomial time unless $P=NP$, so no PTAS exists — and more generally that $k$-flats with $1\le k\le d-2$ admit no PTAS unless $P=NP$; they also proved that in dimension $d=O(\log n)$ no $(2-\varepsilon)$-approximation exists under the Unique Games Conjecture (UGC), a standard conjecture about the hardness of a certain graph-labeling problem. For lines in fixed $d\ge 3$, however, a huge gap remains. The best polynomial-time algorithm, due to Dumitrescu and Tóth, discretizes each line at polynomially many 'relevant' points and solves the resulting group Steiner tree instance, giving an $O(\log^3 n)$-approximation — a ratio inherited from general group Steiner tree and essentially blind to the Euclidean structure of the construction. The SWAT 2022 paper improved the ratio to $O(\log^2 n)$, but only in quasi-polynomial time $n^{O(\log\log n)}$, by combining Arora-style dynamic programming with restricted group Steiner tree techniques; the $\log\log n$ in the exponent comes precisely from the $\log n$ height of Arora's dissection hierarchy and would disappear given an EPTAS for Euclidean TSP running in $O(f(\varepsilon,d)\,n\log n)$ time, which is itself an open problem. On the lower-bound side, group Steiner tree is known to admit no $\log^{2-\varepsilon}n$-approximation (Halperin and Krauthgamer), with matching quasi-polynomial-time tightness of order $\Omega(\log^2 n/(\log\log n)^{3/2})$ under the Projection Games Conjecture (PGC) — a conjecture about label-cover-style constraint systems — by Grandoni, Laekhanukit, and Li; whether any of this hardness transfers to the highly structured (collinear-group) Euclidean instances produced by the reduction from lines is unknown. The frontier question is exactly the one posed in the paper's conclusion.

Problem Statement

The problem, stated in the conclusion of Antoniadis, Kisfaludi-Bak, Laekhanukit, and Vaz (SWAT 2022) as 'perhaps the most important question related to TSPN', is a prove-or-refute question. Either exhibit a polynomial-time algorithm that, given any $n$ lines in $\mathbb{R}^3$, returns a closed tour intersecting every line and having total Euclidean length at most $C$ times the optimal tour length, for an absolute constant $C$ independent of the instance; or prove that no such constant-factor polynomial-time approximation exists — that is, that for every constant $C>0$ a polynomial-time $C$-approximation is hard under a standard complexity assumption such as $P\ne NP$ or the UGC. The input lines are arbitrary (any orientations and positions; the neighborhoods are unbounded full lines, not segments), and no restriction may be added to the input. The source paper additionally poses two companion directions that probe the same upper/lower gap from its two sides and are recorded here as stated facets: (i) whether the $\Omega(\log^2 n/(\log\log n)^{3/2})$ inapproximability known for general group Steiner tree under the Projection Games Conjecture transfers to the geometric instances arising from lines or, more generally, $k$-dimensional flats in $\mathbb{R}^d$; and (ii) whether the $O(\log^2 n)$-approximation can be achieved in genuinely polynomial time.

References

1. Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit, Daniel Vaz. On the Approximability of the Traveling Salesman Problem with Line Neighborhoods. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), LIPIcs vol. 227, article 10, 2022. DOI: 10.4230/LIPIcs.SWAT.2022.10; arXiv:2008.12075. https://doi.org/10.4230/LIPIcs.SWAT.2022.10 (source paper; arXiv: https://arxiv.org/abs/2008.12075)
2. Adrian Dumitrescu, Csaba D. Tóth. The Traveling Salesman Problem for Lines, Balls, and Planes. ACM Transactions on Algorithms 12(3), article 43, 2016. DOI: 10.1145/2850418. https://doi.org/10.1145/2850418
3. Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma, Kevin Schewior. A PTAS for Euclidean TSP with Hyperplane Neighborhoods. ACM Transactions on Algorithms 16(3), article 38 (38:1–38:16), 2020; preliminary version in SODA 2019, pages 1089–1105. DOI: 10.1145/3383466. https://doi.org/10.1145/3383466
4. Adrian Dumitrescu. The Traveling Salesman Problem for Lines and Rays in the Plane. Discrete Mathematics, Algorithms and Applications 4(4), article 1250044, 2012. DOI: 10.1142/S1793830912500449. https://doi.org/10.1142/S1793830912500449
5. Sanjeev Arora. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometric Problems. Journal of the ACM 45(5), pages 753–782, 1998. DOI: 10.1145/290179.290180. https://doi.org/10.1145/290179.290180
6. Fabrizio Grandoni, Bundit Laekhanukit, Shi Li. O(log^2 k / log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), pages 253–264. DOI: 10.1145/3313276.3316349; arXiv:1811.03020. https://arxiv.org/abs/1811.03020
7. Eran Halperin, Robert Krauthgamer. Polylogarithmic Inapproximability. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pages 585–594. DOI: 10.1145/780542.780628. https://doi.org/10.1145/780542.780628
8. Benyamin Ghaseminia, Mohammad R. Salavatipour. A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length. arXiv:2504.02190, 2025. DOI: 10.48550/arXiv.2504.02190. https://arxiv.org/abs/2504.02190