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.$ Currently, the best known bounds are $0.6277 leq beta leq 0.90380$, due to Gaudio and Jaillet (2019) and Carlsson and Yu (2023), respectively. The upper bound was derived using a computer-aided approach that is amenable to lower bounds with improved computation speed. In this paper, we show via simulation and concentration analysis that future improvement of the $0.90380$ is limited to $sim0.88$. Moreover, we provide an alternative tour-constructing heuristic that, via simulation, could potentially improve the upper bound to $sim0.85$. Our approach builds on a prior emph{band-traversal} strategy, initially proposed by Beardwood et al. (1959) and subsequently refined by Carlsson and Yu (2023): divide the unit square into bands of height $Theta(1/sqrt{n})$, construct paths within each band, and then connect the paths to create a TSP tour. Our approach allows paths to cross bands, and takes advantage of pairs of points in adjacent bands which are close to each other. A rigorous numerical analysis improves the upper bound to $0.90367$.