A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909581120110592 |
|---|---|
| author | Ghaseminia, Benyamin Salavatipour, Mohammad R. |
| author_facet | Ghaseminia, Benyamin Salavatipour, Mohammad R. |
| contents | 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, λ]$ for any constant value $λ\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\sqrt2$ 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 + ε)$-factor approximation for an instance of the problem for $n$ segments with lengths in $ [1,λ] $ in time $ n^{O(λ/ε^3)} $. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_02190 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length Ghaseminia, Benyamin Salavatipour, Mohammad R. Data Structures and Algorithms Computational Geometry 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, λ]$ for any constant value $λ\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\sqrt2$ 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 + ε)$-factor approximation for an instance of the problem for $n$ segments with lengths in $ [1,λ] $ in time $ n^{O(λ/ε^3)} $. |
| title | A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2504.02190 |