Editing Travelling salesman problem (section)

====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>.