A073008 - OEIS

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

(list; constant; graph; refs; listen; history; text; internal format)

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