A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length

Abstract

We consider the Travelling Salesman Problem with Neighbourhoods (TSPN) on the Euclidean plane (${\mathbb{R}}^2$) and present a Polynomial-Time Approximation Scheme (PTAS) when the neighbourhoods are parallel line segments with lengths between $[1,\lambda ]$ for any constant value $\lambda \ge 1$. In TSPN (which generalizes classic TSP), each client represents a set (or neighbourhood) of points in a metric and the goal is to find a minimum cost TSP tour that visits at least one point from each client set. In the Euclidean setting, each neighbourhood is a region on the plane. TSPN is significantly more difficult than classic TSP even in the Euclidean setting, as it captures group TSP. A notable case of TSPN is when each neighbourhood is a line segment. Although there are PTASs for when neighbourhoods are fat objects (with limited overlap), TSPN over line segments is APX-hard even if all the line segments have unit length. For parallel (unit) line segments, the best approximation factor is $3\sqrt{2}$ from more than two decades ago [DM03]. The PTAS we present in this paper settles the approximability of this case of the problem. Our algorithm finds a $(1+\epsilon )$-factor approximation for an instance of the problem for $n$ segments with lengths in $[1,\lambda ]$ in time $n^{O(\lambda /{\epsilon }^3)}$.

An extended abstract to appear in proceedings of SoCG 2025