Time complexity of the Analyst's Traveling Salesman algorithm
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917631929352192 |
|---|---|
| author | Ramirez, Anthony Vellis, Vyron |
| author_facet | Ramirez, Anthony Vellis, Vyron |
| contents | The Analyst's Traveling Salesman Problem asks for conditions under which a (finite or infinite) subset of $\mathbb{R}^N$ is contained on a curve of finite length. We show that for finite sets, the algorithm constructed by Schul (2007)and Badger-Naples-Vellis (2019) that solves the Analyst's Traveling Salesman Problem has polynomial time complexity and we determine the sharp exponent. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_10314 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Time complexity of the Analyst's Traveling Salesman algorithm Ramirez, Anthony Vellis, Vyron Data Structures and Algorithms Computational Complexity Computational Geometry Metric Geometry The Analyst's Traveling Salesman Problem asks for conditions under which a (finite or infinite) subset of $\mathbb{R}^N$ is contained on a curve of finite length. We show that for finite sets, the algorithm constructed by Schul (2007)and Badger-Naples-Vellis (2019) that solves the Analyst's Traveling Salesman Problem has polynomial time complexity and we determine the sharp exponent. |
| title | Time complexity of the Analyst's Traveling Salesman algorithm |
| topic | Data Structures and Algorithms Computational Complexity Computational Geometry Metric Geometry |
| url | https://arxiv.org/abs/2202.10314 |