Snyder, Timothy Law; Steele, J. Michael A priori bounds on the Euclidean traveling salesman. (English) Zbl 0831.68077 SIAM J. Comput. 24, No. 3, 665-671 (1995). Summary: 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 \(d > 2\) are also sketched. The presence of the logarithmic term in (1) is engaging becasue 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\). Cited in 2 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 05C45 Eulerian and Hamiltonian graphs 90C35 Programming involving graphs or networks 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) Keywords:Euclidean traveling salesman problem PDFBibTeX XMLCite \textit{T. L. Snyder} and \textit{J. M. Steele}, SIAM J. Comput. 24, No. 3, 665--671 (1995; Zbl 0831.68077) Full Text: DOI