Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Travelling salesman problem
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
===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>.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)