Closed curve covering and multiagent TSP ratios
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_ | 1866908536682840064 |
|---|---|
| author | Dillon, Travis Dumitrescu, Adrian |
| author_facet | Dillon, Travis Dumitrescu, Adrian |
| contents | How efficiently can a closed curve of unit length in $\mathbb{R}^d$ be covered by $k$ closed curves so as to minimize the maximum length of the $k$ curves? We show that the maximum length is at most $2k^{-1} - \frac{1}{4} k^{-4}$ for all $k\geq 2$ and $d \geq 2$. As a first byproduct, we show that $k$ agents can traverse a Euclidean TSP instance significantly faster than a single agent. We thereby sharpen recent planar results by Berendsohn, Kim, and Kozma (2025) and extend these improvements to all dimensions. As a second byproduct, we obtain a linear time approximation algorithm with ratio $2 - \frac{1}{4} k^{-3}$ for covering any closed polygonal curve in $\mathbb{R}^d$ by $k$ closed curves so that the maximum length of an individual curve is minimized. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_16675 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Closed curve covering and multiagent TSP ratios Dillon, Travis Dumitrescu, Adrian Metric Geometry Discrete Mathematics How efficiently can a closed curve of unit length in $\mathbb{R}^d$ be covered by $k$ closed curves so as to minimize the maximum length of the $k$ curves? We show that the maximum length is at most $2k^{-1} - \frac{1}{4} k^{-4}$ for all $k\geq 2$ and $d \geq 2$. As a first byproduct, we show that $k$ agents can traverse a Euclidean TSP instance significantly faster than a single agent. We thereby sharpen recent planar results by Berendsohn, Kim, and Kozma (2025) and extend these improvements to all dimensions. As a second byproduct, we obtain a linear time approximation algorithm with ratio $2 - \frac{1}{4} k^{-3}$ for covering any closed polygonal curve in $\mathbb{R}^d$ by $k$ closed curves so that the maximum length of an individual curve is minimized. |
| title | Closed curve covering and multiagent TSP ratios |
| topic | Metric Geometry Discrete Mathematics |
| url | https://arxiv.org/abs/2506.16675 |