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 (1959) proved the existence of a universal constant β2 whose best bounds are 0.625 ≤ β2 ≤ 0.92116. Building upon an approach proposed by Steinerberger (2015), we present a computer-aided proof that improves its upper bound to β2 < 0.90304.

## Article

Download

View A new upper bound of the Euclidean TSP constant