Gaussian fluctuations of the optimal Euclidean traveling-salesman tour
Let $X_1, X_2, \ldots$ be independent uniform points in $[0,1]^2$ and let $L_n$ be the length of a shortest closed polygonal tour through $X_1, \dots, X_n$. Beardwood, Halton and Hammersley proved that $L_n/\sqrt{n}$ converges almost surely to a positive constant. Steele showed that $\operatorname{Var}(L_n)$ is bounded independently of $n$, and Rhee proved a lower bound on the fluctuations of $L_n$ of the same order. For the length of the Euclidean minimal spanning tree of such points, Kesten and Lee proved a central limit theorem, and Chatterjee and Sen gave a rate of convergence for its Poissonized version.
Problem. Does $(L_n - \mathbb{E} L_n)/\sqrt{\operatorname{Var}(L_n)}$ converge in distribution to the standard normal law as $n \to \infty$? The tour must be globally optimal; the length of a tour produced by a heuristic is not substituted for $L_n$.
Source: Steele (1992), §8.8, the central limit problem; asked explicitly in the report of the NSF workshop on Current and Emerging Research Opportunities in Probability (2002), §1.2. Stated with the exact variance normalisation by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO, OC
- Keywords
- AIM Open Applied Problems, central limit theorems, geometric probability, traveling salesman problem
References
@incollection{steele1992,
author = {Steele, J. Michael},
title = {Probability and problems in {E}uclidean combinatorial optimization},
booktitle = {Probability and Algorithms},
publisher = {National Academy Press},
address = {Washington, DC},
year = {1992},
pages = {109--130},
doi = {10.17226/2026},
note = {Chapter 8; also in Statist. Sci. 8 (1993), 48--56, doi:10.1214/ss/1177011083},
}
@misc{probrep2002,
title = {Current and Emerging Research Opportunities in Probability},
howpublished = {Report of the workshop held at the National Science Foundation, 29--31 May 2002},
year = {2002},
url = {https://www.stat.berkeley.edu/~aldous/Real-World/probrep2002.html},
}
@article{beardwood1959,
author = {Beardwood, Jillian and Halton, J. H. and Hammersley, J. M.},
title = {The shortest path through many points},
journal = {Proc. Cambridge Philos. Soc.},
volume = {55},
number = {4},
year = {1959},
pages = {299--327},
doi = {10.1017/S0305004100034095},
}
@article{steele1981,
author = {Steele, J. Michael},
title = {Complete convergence of short paths and {K}arp's algorithm for the {TSP}},
journal = {Math. Oper. Res.},
volume = {6},
number = {3},
year = {1981},
pages = {374--378},
doi = {10.1287/moor.6.3.374},
}
@article{rhee1991,
author = {Rhee, Wansoo T.},
title = {On the fluctuations of the stochastic traveling salesperson problem},
journal = {Math. Oper. Res.},
volume = {16},
number = {3},
year = {1991},
pages = {482--489},
doi = {10.1287/moor.16.3.482},
}
@article{kesten1996,
author = {Kesten, Harry and Lee, Sungchul},
title = {The central limit theorem for weighted minimal spanning trees on random points},
journal = {Ann. Appl. Probab.},
volume = {6},
number = {2},
year = {1996},
pages = {495--527},
doi = {10.1214/aoap/1034968141},
}
@article{chatterjee2017,
author = {Chatterjee, Sourav and Sen, Sanchayan},
title = {Minimal spanning trees and {S}tein's method},
journal = {Ann. Appl. Probab.},
volume = {27},
number = {3},
year = {2017},
pages = {1588--1645},
doi = {10.1214/16-AAP1239},
eprint = {1307.1661},
archivePrefix = {arXiv},
}
@misc{aim-euclidean-tsp-clt,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Gaussian fluctuations of the optimal Euclidean traveling-salesman tour}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/274-euclidean-tsp-clt.md},
note = {Entry 274 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00430, "Gaussian fluctuations of the optimal Euclidean traveling-salesman tour", clopen.solutions.