1. |
- Wästlund, Johan, 1971
(author)
-
The mean field traveling salesman and related problems
- 2010
-
In: Acta Mathematica. - : International Press of Boston. - 0001-5962. ; 204:1, s. 91-150
-
Journal article (peer-reviewed)abstract
- 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 -> a, the cost of the minimum traveling salesman tour converges in probability to a certain number, approximately 2.0415, which is characterized analytically.
|
|