Approximating 1-dimensional TSP Requires Omega(n log n) Comparisons
arXiv:1303.2920
Abstract
We give a short proof that any comparison-based n^(1-epsilon)-approximation algorithm for the 1-dimensional Traveling Salesman Problem (TSP) requires Omega(n log n) comparisons.
Superseded by "On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees", by Das et al; Algorithmica 19:447-460 (1997)