Balanced TSP partitioning
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916690917326848 |
|---|---|
| author | Berendsohn, Benjamin Aram Kim, Hwi Kozma, László |
| author_facet | Berendsohn, Benjamin Aram Kim, Hwi Kozma, László |
| contents | The traveling salesman problem (TSP) famously asks for a shortest tour that a salesperson can take to visit a given set of cities in any order. In this paper, we ask how much faster $k \ge 2$ salespeople can visit the cities if they divide the task among themselves. We show that, in the two-dimensional Euclidean setting, two salespeople can always achieve a speedup of at least $\frac12 + \frac1π\approx 0.818$, for any given input, and there are inputs where they cannot do better. We also give (non-matching) upper and lower bounds for $k \geq 3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_10657 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Balanced TSP partitioning Berendsohn, Benjamin Aram Kim, Hwi Kozma, László Computational Geometry Data Structures and Algorithms The traveling salesman problem (TSP) famously asks for a shortest tour that a salesperson can take to visit a given set of cities in any order. In this paper, we ask how much faster $k \ge 2$ salespeople can visit the cities if they divide the task among themselves. We show that, in the two-dimensional Euclidean setting, two salespeople can always achieve a speedup of at least $\frac12 + \frac1π\approx 0.818$, for any given input, and there are inputs where they cannot do better. We also give (non-matching) upper and lower bounds for $k \geq 3$. |
| title | Balanced TSP partitioning |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.10657 |