An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
arXiv:2602.11250v1 Announce Type: new Abstract: Consider $n$ points generated uniformly at random in the unit square, and let $L_n$ be the length of their optimal traveling salesman tour. Beardwood, Halton, and Hammersley (1959) showed $L_n / sqrt n to beta$ almost surely as $nto infty$ for some constant $beta$. The exact value of $beta$ is unknown but estimated to be approximately $0.71$ (Applegate, Bixby, Chv’atal, Cook 2011). Beardwood et al. further showed that $0.625 leq beta leq 0.92116.$ […]