Time complexity of the analyst's traveling salesman algorithm

DOI10.4115/jla.2024.16.2arXiv2202.10314OpenAlexW4392794137MaRDI QIDQ6200929

Vyron Vellis, Unnamed Author

Publication date: 25 March 2024

Published in: Journal of Logic and Analysis (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2202.10314

zbMATH Keywords

approximation algorithmspolynomial-time approximation schemetraveling salesperson problemanalyst traveling salesman problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Length, area, volume, other geometric measure theory (28A75)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multiscale analysis of 1-rectifiable measures. II: Characterizations
• Rectifiable sets and the traveling salesman problem
• Subsets of rectifiable curves in Hilbert space-the analyst's TSP
• The Euclidean traveling salesman problem is NP-complete
• The traveling salesman problem and its variations
• Worst-case analysis of a new heuristic for the travelling salesman problem
• Hölder curves and parameterizations in the Analyst's traveling salesman theorem
• The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• Approximate Traveling Salesman Algorithms
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Characterization of Subsets of Rectifiable Curves in R ⁿ
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem