%I #26 Feb 15 2020 08:22:09

%S 7,1,4,7,8,2,7,0,0,7,9,1,2,9,4,2,7,2,0,1,8,9,8,4,8,7,9,6,2,1,0,8,4,0,

%T 9,6,7,3,1,3,4,5,5,9,7,0,9,4,4,3,0,3,1,9,3,9,6,4,5,7,0,0,4,1,1,5,4,6,

%U 1,1,7,7,3,8,3,3,5,8,7,9,7,0,6,7,7,0,2,1,3,4,1,3,0,9,6,2,9,4,5,3,3,5,6,1,5

%N Decimal expansion of the Traveling Salesman constant.

%C From _Elijah Beregovsky_, Jan 10 2020: (Start)

%C In 1959 J. Beardwood, J. H. Halton and J. M. Hammersley showed that the shortest tour through N random uniformly distributed points in a bounded plane region of area A approaches K*sqrt(N*A), where K is the Traveling Salesman constant, as N approaches infinity. They also proved that 5/8 <= K < 0.922.

%C In 2015 S. Steinerberger slightly improved both bounds.

%C In 1995 P. Moscato and N. G. Norman proved that a plane-filling curve called MNPeano is the shortest tour through the set of points defined by MNPeano and observed that the asymptotic expected length of this curve is given by (4/153)*(1+2*sqrt(2))*sqrt(51)*sqrt(N*A), which is very close to the empirical value of the traveling salesman constant.

%C (End)

%D J. Beardwood, J. H. Halton and J. M. Hammersley, The shortest path through many points, Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 55, No. 4, 1959, pp. 299-327.

%H P. Moscato and M. G. Norman, <a href="https://pdfs.semanticscholar.org/2075/9787c1bcc785c1b18c2b2ef00dd4016b028b.pdf?_ga=2.268871473.1100463513.1578586886-1196856132.1578497585">An analysis of the performance of traveling salesman heuristics on infinite-size fractal instanced in the Euclidean plane</a>

%H Simon Plouffe, <a href="https://web.archive.org/web/20080205213007/http://www.worldwideschool.org/library/books/sci/math/MiscellaneousMathematicalConstants/chap88.html">Traveling Salesman Constant</a>

%H J. M. Steele, <a href="http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/PaWCAo.pdf">Probabilistic and worst case analyses of classical problems of combinatorial optimization in Euclidean space</a>, Mathematics of Operations Research, Vol. 15, No. 4 (Nov., 1990), pp. 749-770.

%H Stefan Steinerberger, <a href="https://arxiv.org/abs/1311.6338">New bounds for the traveling salesman constant</a>, arXiv:1311.6338 [math.PR], 2013-2014.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TravelingSalesmanConstants.html">Traveling Salesman Constants</a>

%F Conjectured to be equal to (4/153)*(1+2*sqrt(2))*sqrt(51).

%e 0.7147827007912942720189848796210840967313...

%K cons,nonn

%O 0,1

%A _Robert G. Wilson v_, Aug 03 2002