General Spacefilling Curve Heuristics and Limit Theory for the Traveling Salesman Problem
Jun Ping Gao, J. Michael Steele · Journal of Complexity · 1994
The tour given by the spacefilling curve heuristic applied to a random sample of points from the unit square differs in subtle ways from the shortest tour through those points. In particular, the expected length of the heuristic tour is found to be asymptotic to √n times a periodic function of log n for a broad class of spacefilling curves. The theory is developed further by detailing the self-similarity properties of the spacefilling curve that are useful for obtaining the asymptotics of the expected length of the heuristic path. Finally, the theory of martingales is applied to obtain tail bounds that yield rigorous almost sure asymptotics for the length of the heuristic tours.