The mean field traveling salesman and related problems

By Johan Wästlund. 2010

53 citations recorded by the source corpus.

The edges of a complete graph on n vertices are assigned i.i.d. random costs from a distribution for which the interval [0, t] has probability asymptotic to t as t→0 through positive values. In this so called pseudo-dimension 1 mean field model, we study several optimization problems, of which the traveling salesman is the best known. We prove that, as n→∞, the cost of the minimum traveling salesman tour converges in probability to a certain number, approximately 2.0415, which is characterized analytically.

Subfields: Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/fc1a75b491ef2d17063e4841224f37735767bfe5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

A short survey of Stein's method (2014, background): “Mean field versions of these problems, which look at complete graphs instead of lattices or Euclidean points, have been analyzed in great depth in a remarkable set of papers by Wästlund [85, 86].”