A Priori Bounds on the Euclidean Traveling Salesman
Timothy Law Snyder, John M. Steele · SIAM Journal on Computing · 1995
It is proved that there are constants $c_{1}$, $c_{2}$, and $c_{3}$ such that for any set S of n points in the unit square and for any minimum-length tour T of S the sum of squares of the edge lengths of T is bounded by $c_{1} \log n$. (2) the number of edges having length t or greater in T is at most $c_{2}/t^{2}$, and (3) the sum of edge lengths of any subset E of T is bounded by $c_{3}|E|^{1/2}$. The second and third bounds are independent of the number of points in S, as well as their locations. Extensions to dimensions $d > 2$ are also sketched. The presence of the logarithmic term in (1) is engaging because such a term is not needed in the case of the minimum spanning tree and several analogous problems, and, furthermore, we know that there always exists some tour of S (which perhaps does not have minimal length) for which the sum of squared edges is bounded independently of n.