A New Upper Bound for the Euclidean TSP Constant

Let $X_1,X_2,\dots ,X_n$ be n independent and uniformly distributed random points in a compact region $R\subset {\mathbb{R}}^2$ of area 1. Let $\mathsf{\text{TSP}}(X_1,\dots ,X_n)$ denote the length of the optimal Euclidean traveling salesman tour that traverses all these points. The classical Beardwood-Halton-Hammersley theorem proves the existence of a universal constant ${\beta }_2$ such $\mathsf{\text{TSP}}(X_1,\dots ,X_n)/\sqrt{n}\to {\beta }_2$ almost surely, which satisfies $0.625\le {\beta }_2\le 0.92117$. This paper presents a computer-aided proof using numerical quadrature and decision trees that ${\beta }_2<0.9038$. Although our improvement is still somewhat small, our approach has the advantage that it is primarily limited by computer hardware and is thus amenable to further improvements over time.

History: Accepted by Russell Bent, Area Editor for Network Optimization: Algorithms & Applications.

Funding: This work was supported by the Office of Naval Research [Grants AWD-00008450, N00014-20-S-B001, and N00014-21-1-2208], the California Department of Transportation, and the U.S. Department of Transportation [Grant 69A3551747114].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0538) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0538). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.