A073008 Decimal expansion of the Traveling Salesman constant.

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, 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, 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

Offset

0,1

Comments

From Elijah Beregovsky, Jan 10 2020: (Start)

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.

In 2015 S. Steinerberger slightly improved both bounds.

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.

(End)

References

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.

Links

Table of n, a(n) for n=0..104.

P. Moscato and M. G. Norman, An analysis of the performance of traveling salesman heuristics on infinite-size fractal instanced in the Euclidean plane

Simon Plouffe, Traveling Salesman Constant

J. M. Steele, Probabilistic and worst case analyses of classical problems of combinatorial optimization in Euclidean space, Mathematics of Operations Research, Vol. 15, No. 4 (Nov., 1990), pp. 749-770.

Stefan Steinerberger, New bounds for the traveling salesman constant, arXiv:1311.6338 [math.PR], 2013-2014.

Eric Weisstein's World of Mathematics, Traveling Salesman Constants

Formula

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

Example

0.7147827007912942720189848796210840967313...

Crossrefs

Sequence in context: A199388 A201750 A198825 * A105199 A020791 A367910

Adjacent sequences: A073005 A073006 A073007 * A073009 A073010 A073011

Keyword

cons,nonn

Author

Robert G. Wilson v, Aug 03 2002

Status

approved