A Priori Bounds on the Euclidean Traveling Salesman

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$ (1) 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 $d2$ 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$.