Sökning: id:"swepub:oai:gup.ub.gu.se/118214" >
The mean field trav...
The mean field traveling salesman and related problems
-
- Wästlund, Johan, 1971 (författare)
- Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper, matematik,Department of Mathematical Sciences, Mathematics,Chalmers tekniska högskola,Chalmers University of Technology,University of Gothenburg
-
(creator_code:org_t)
- International Press of Boston, 2010
- 2010
- Engelska.
-
Ingår i: Acta Mathematica. - : International Press of Boston. - 0001-5962. ; 204:1, s. 91-150
- Relaterad länk:
-
https://doi.org/10.1...
-
visa fler...
-
http://dx.doi.org/10...
-
https://gup.ub.gu.se...
-
https://doi.org/10.1...
-
https://research.cha...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
Nyckelord
- random assignment problem
- expected value
- combinatorial optimization
- statistical-mechanics
- minimum assignment
- exact expectations
- finite-size
- spin-glass
- model
- asymptotics
- model
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas