The mean field traveling salesman and related problems

Johan Wästlund Department of Mathematical Sciences, Chalmers University of Technology

TBD mathscidoc:1701.332013

Acta Mathematica, 204, (1), 91-150, 2008.4
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.
No keywords uploaded!
[ Download ] [ 2017-01-08 20:33:54 uploaded by actaadmin ] [ 841 downloads ] [ 0 comments ]
  title={The mean field traveling salesman and related problems},
  author={Johan Wästlund},
  booktitle={Acta Mathematica},
Johan Wästlund. The mean field traveling salesman and related problems. 2008. Vol. 204. In Acta Mathematica. pp.91-150.
Please log in for comment!
Contact us: | Copyright Reserved