A new upper bound of the Euclidean TSP constant

Let X1, X2, . . . , Xn be n independent and uniformly distributed random points in a compact region R ⊂ R2 of area 1. Let TSP(X1, . . . , Xn) 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(X1, . . . , Xn)/ √ 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.90304. 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.

Article

Download

View PDF