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→∞, the cost of the minimum traveling salesman tour converges in probability to a certain number, approximately 2.0415, which
is characterized analytically.
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.
- Content Type Journal Article
- DOI 10.1007/s11511-010-0046-7
- Authors
- Johan Wästlund, Chalmers University of Technology Department of Mathematical Sciences SE-412 96 Gothenburg Sweden
- Journal Acta Mathematica
- Online ISSN 1871-2509
- Print ISSN 0001-5962
No hay comentarios:
Publicar un comentario
Nota: solo los miembros de este blog pueden publicar comentarios.