The Bright Side of Simple Heuristics for the TSP

The greedy and nearest-neighbor TSP heuristics can both have log n approximation factors from optimal in worst case, even just for n points in Euclidean space. In this note, we show that this approximation factor is only realized when the optimal tour is unusually short. In particular, for points from any fixed d-Ahlfor's regular metric space (which includes any d-manifold like the d-cube [0,1]ᵈ in the case d is an integer but also fractals of dimension d when d is real-valued), our results imply that the greedy and nearest-neighbor heuristics have additive errors from optimal on the order of the optimal tour length through random points in the same space, for $d>1$.