Editing Travelling salesman problem (section)

===Path length for random sets of points in a square===
Suppose <math>X_1,\ldots,X_n</math> are <math>n</math> independent random variables with uniform distribution in the square <math>[0,1]^2</math>, and let <math>L^\ast_n</math> be the shortest path length (i.e. TSP solution) for this set of points, according to the usual [[Euclidean distance]]. It is known{{sfnp|Beardwood|Halton|Hammersley|1959}} that, almost surely,

::<math>\frac{L^*_n}{\sqrt n}\rightarrow \beta\qquad\text{when }n\to\infty,</math>

where <math>\beta</math> is a positive constant that is not known explicitly. Since <math>L^*_n\le2\sqrt n+2</math> (see below), it follows from [[bounded convergence theorem]] that <math>\beta=\lim_{n\to\infty} \mathbb E[L^*_n]/\sqrt n</math>, hence lower and upper bounds on <math>\beta</math> follow from bounds on <math>\mathbb E[L^*_n]</math>.

The [[Almost surely|almost-sure]] limit <math>\frac{L^*_n}{\sqrt n}\rightarrow \beta</math> as <math>n\to\infty</math> may not exist if the independent locations <math>X_1,\ldots,X_n</math> are replaced with observations from a stationary ergodic process with uniform marginals.<ref name="as2016">{{citation
 | doi = 10.1214/15-AAP1142
 | last1 = Arlotto | first1 = Alessandro
 | last2 = Steele | first2 = J. Michael | author2-link = J. Michael Steele
 | journal = The Annals of Applied Probability 
 | pages = 2141–2168
 | title = Beardwood–Halton–Hammersley theorem for stationary ergodic sequences: a counterexample
 | volume = 26
 | issue = 4
 | year = 2016| arxiv = 1307.0221| s2cid = 8904077 }}</ref>

====Upper bound====
*One has <math>L^*\le 2\sqrt{n}+2</math>, and therefore <math>\beta\leq 2</math>, by using a naïve path which visits monotonically the points inside each of <math>\sqrt n</math> slices of width <math>1/\sqrt{n}</math> in the square.
*Few<ref>{{cite journal|last1=Few|first1=L.|title=The shortest path and the shortest road through n points|journal=[[Mathematika]]|date=1955|volume=2|issue=2|pages=141–144|doi=10.1112/s0025579300000784 }}</ref> proved <math>L^*_n\le\sqrt{2n}+1.75</math>, hence <math>\beta\le\sqrt 2</math>, later improved by Karloff (1987): <math>\beta\le0.984\sqrt2</math>.
* Fietcher<ref>{{cite journal|last1=Fiechter|first1=C.-N.|title=A parallel tabu search algorithm for large traveling salesman problems|journal=Disc. Applied Math.|date=1994|volume=51|issue=3|pages=243–267 |doi=10.1016/0166-218X(92)00033-I|doi-access=free}}</ref> empirically suggested an upper bound of <math>\beta\le 0.73\dots</math>.

====Lower bound====
*By observing that <math>\mathbb E[L^*_n]</math> is greater than <math>n</math> times the distance between <math>X_0</math> and the closest point <math>X_i\ne X_0</math>, one gets (after a short computation)

::<math>\mathbb E[L^*_n]\ge\tfrac{1}{2} \sqrt{n}.</math>

*A better lower bound is obtained by observing that <math>\mathbb E[L^*_n]</math> is greater than <math>n/2</math> times the sum of the distances between <math>X_0</math> and the closest and second closest points <math>X_i,X_j\ne X_0</math>, which gives{{sfnp|Beardwood|Halton|Hammersley|1959}}

::<math>\mathbb E[L^*_n]\ge \bigl(\tfrac14 + \tfrac38\bigr)\sqrt{n} = \tfrac{5}{8}\sqrt{n},</math>

*The currently-best{{When|date=April 2024}} lower bound is{{sfnp|Steinerberger|2015}}
::<math>\mathbb E[L^*_n]\ge \bigl(\tfrac58 + \tfrac{19}{5184}\bigr)\sqrt{n},</math>

*Held and Karp gave a polynomial-time algorithm that provides numerical lower bounds for <math>L^*_n</math>, and thus for <math>\beta(\simeq L^*_n/{\sqrt n})</math>, which seem to be good up to more or less 1%.<ref>{{cite journal|last1=Held|first1=M.|last2=Karp|first2=R.M.|title=The Traveling Salesman Problem and Minimum Spanning Trees|journal=Operations Research|date=1970|volume=18|issue=6|pages=1138–1162 |doi=10.1287/opre.18.6.1138 }}</ref><ref>{{cite journal
| last1=Goemans | first1=Michel X. | authorlink1=Michel Goemans
| last2=Bertsimas | first2=Dimitris J. | authorlink2=Dimitris Bertsimas
| title=Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem
| journal=[[Mathematics of Operations Research]]
| date=1991
| volume=16
| issue=1
| pages=72–89
| doi=10.1287/moor.16.1.72}}</ref> In particular, David S. Johnson obtained a lower bound by computer experiment:<ref>{{cite web|url=https://about.att.com/error.html|title=error |website=about.att.com}}</ref>

::<math>L^*_n\gtrsim 0.7080\sqrt{n}+0.522,</math>

where 0.522 comes from the points near the square boundary which have fewer neighbours, and Christine L. Valenzuela and [[Antonia J. Jones]] obtained the following other numerical lower bound:<ref>[http://users.cs.cf.ac.uk/Antonia.J.Jones/Papers/EJORHeldKarp/HeldKarp.pdf Christine L. Valenzuela and Antonia J. Jones] {{webarchive|url=https://web.archive.org/web/20071025205411/http://users.cs.cf.ac.uk/Antonia.J.Jones/Papers/EJORHeldKarp/HeldKarp.pdf |date=25 October 2007 }}</ref>
::<math>L^*_n\gtrsim 0.7078\sqrt{n}+0.551</math>.