### Time complexity of the analyst's traveling salesman algorithm

#### Abstract

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.

#### Keywords

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

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

Journal of Logic and Analysis ISSN: 1759-9008