Approximation and Hardness of Polychromatic TSP
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909677487390720 |
|---|---|
| author | Schibler, Thomas Suri, Subhash Xue, Jie |
| author_facet | Schibler, Thomas Suri, Subhash Xue, Jie |
| contents | We introduce the Polychromatic Traveling Salesman Problem (PCTSP), where the input is an edge weighted graph whose vertices are partitioned into $k$ equal-sized color classes, and the goal is to find a minimum-length Hamiltonian cycle that visits the classes in a fixed cyclic order. This generalizes the Bipartite TSP (when $k = 2$) and the classical TSP (when $k = n$). We give a polynomial-time $(3 - 2 * 10^{-36})$-approximation algorithm for metric PCTSP. Complementing this, we show that Euclidean PCTSP is APX-hard even in $R^2$, ruling out the existence of a PTAS unless P = NP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04974 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximation and Hardness of Polychromatic TSP Schibler, Thomas Suri, Subhash Xue, Jie Computational Geometry We introduce the Polychromatic Traveling Salesman Problem (PCTSP), where the input is an edge weighted graph whose vertices are partitioned into $k$ equal-sized color classes, and the goal is to find a minimum-length Hamiltonian cycle that visits the classes in a fixed cyclic order. This generalizes the Bipartite TSP (when $k = 2$) and the classical TSP (when $k = n$). We give a polynomial-time $(3 - 2 * 10^{-36})$-approximation algorithm for metric PCTSP. Complementing this, we show that Euclidean PCTSP is APX-hard even in $R^2$, ruling out the existence of a PTAS unless P = NP. |
| title | Approximation and Hardness of Polychromatic TSP |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2507.04974 |