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 ] [ 223 downloads ] [ 0 comments ]
@inproceedings{johan2008the,
  title={The mean field traveling salesman and related problems},
  author={Johan Wästlund},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170108203354846737722},
  booktitle={Acta Mathematica},
  volume={204},
  number={1},
  pages={91-150},
  year={2008},
}
Johan Wästlund. The mean field traveling salesman and related problems. 2008. Vol. 204. In Acta Mathematica. pp.91-150. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170108203354846737722.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved