A New Upper Bound for the Euclidean TSP Constant

Let X 1 , X 2 , … , X n be n independent and uniformly distributed random points in a compact region R ⊂ R 2 of area 1. Let 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 such TSP ( X 1 , … , X n ) / n → β 2 almost surely, which satisfies 0.625 ≤ β 2 ≤ 0.92117 . This paper presents a computer-aided proof using numerical quadrature and decision trees that β 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.