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

Benyamin Ghaseminia, Mohammad R. Salavatipour

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 ne…