Time complexity of the analyst's traveling salesman algorithm

Anthony Ramirez, Vyron Vellis


The Analyst's Traveling Salesman Problem asks for conditions under which a (finite or infinite) subset of $\R^N$ is contained on a curve of finite length. We show that for finite sets, the algorithm constructed in \cite{Schul-Hilbert,BNV} that solves the Analyst's Traveling Salesman Problem has polynomial time complexity and we determine the sharp exponent.


approximation algorithms, polynomial-time approximation scheme, traveling salesperson problem, analyst traveling salesman problem

Full Text:

2. [PDF]

DOI: https://doi.org/10.4115/jla.2024.16.2

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Journal of Logic and Analysis ISSN:  1759-9008