A New Upper Bound for the Euclidean TSP Constant
John Gunnar Carlsson, Julien Yu
INFORMS Journal on Computing Β· 2026 Β· Volume 38 Β· Issue 2
Abstract
Let π 1 , π 2 , β¦ , π π X 1 , X 2 , β¦ , X n be n independent and uniformly distributed random points in a compact region π β β 2 R β R 2 of area 1. Let π³ π² π― β‘ ( π 1 , β¦ , π π ) TSP β‘ ( X 1 , β¦ , 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 π½ 2 Ξ² 2 such π³ π² π― β‘ ( π 1 , β¦ , π π ) / β π β π½ 2 TSP β‘ ( X 1 , β¦ , X n ) / n β Ξ² 2 almost surely, which satisfies 0 . 6 2 5 β€ π½ 2 β€ 0 . 9 2 1 1 7 0.625 β€ Ξ² 2 β€ 0.92117 . This paper presents a computer-aided proof using numerical quadrature and decision trees that π½ 2 < 0 . 9 0 3 8 Ξ² 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/ .
Keywords
490 networksβgraphs, traveling salesman, 514 networksβgraphs: stochastic, 489 networksβgraphs, theory
Enable JavaScript for citation tools and additional paper interactions.