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

We consider the Travelling Salesman Problem with Neighbourhoods (TSPN) on the Euclidean plane ($\RR^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 \textbf{APX}-hard even if all the line segments have unit length. For parallel (unit) line segments, the best approximation factor is $3\sqrt2$ from more than two decades ago \cite{DM03}. The PTAS we present in this paper settles the approximability of this case of the problem. Our algorithm finds a $ (1 + \eps) $-factor approximation for an instance of the problem for $n$ segments with lengths in $ [1,\lambda] $ in time $ n^{O(\lambda/\eps^3)} $.