A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929251051110400 |
|---|---|
| author | Baligács, Júlia Disser, Yann Feldmann, Andreas Emil Zych-Pawlewicz, Anna |
| author_facet | Baligács, Júlia Disser, Yann Feldmann, Andreas Emil Zych-Pawlewicz, Anna |
| contents | In the Tricolored Euclidean Traveling Salesperson problem, we are given~$k=3$ sets of points in the plane and are looking for disjoint tours, each covering one of the sets. Arora (1998) famously gave a PTAS based on ``patching'' for the case $k=1$ and, recently, Dross et al.~(2023) generalized this result to~$k=2$. Our contribution is a $(5/3+ε)$-approximation algorithm for~$k=3$ that further generalizes Arora's approach. It is believed that patching is generally no longer possible for more than two tours. We circumvent this issue by either applying a conditional patching scheme for three tours or using an alternative approach based on a weighted solution for $k=2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_13938 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP Baligács, Júlia Disser, Yann Feldmann, Andreas Emil Zych-Pawlewicz, Anna Data Structures and Algorithms In the Tricolored Euclidean Traveling Salesperson problem, we are given~$k=3$ sets of points in the plane and are looking for disjoint tours, each covering one of the sets. Arora (1998) famously gave a PTAS based on ``patching'' for the case $k=1$ and, recently, Dross et al.~(2023) generalized this result to~$k=2$. Our contribution is a $(5/3+ε)$-approximation algorithm for~$k=3$ that further generalizes Arora's approach. It is believed that patching is generally no longer possible for more than two tours. We circumvent this issue by either applying a conditional patching scheme for three tours or using an alternative approach based on a weighted solution for $k=2$. |
| title | A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.13938 |