transparent gif

 

Ej inloggad.

Göteborgs universitets publikationer

The mean field traveling salesman and related problems

Författare och institution:
Johan Wästlund (Institutionen för matematiska vetenskaper, matematik, Chalmers/GU)
Publicerad i:
Acta Mathematica, 204 ( 1 ) s. 91-150
ISSN:
0001-5962
Publikationstyp:
Artikel, refereegranskad vetenskaplig
Publiceringsår:
2010
Språk:
engelska
Fulltextlänk:
Sammanfattning (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.
Ämne (baseras på Högskoleverkets indelning av forskningsämnen):
NATURVETENSKAP ->
Matematik
Nyckelord:
random assignment problem, expected value, combinatorial optimization, statistical-mechanics, minimum assignment, exact expectations, finite-size, spin-glass, model, asymptotics
Postens nummer:
118214
Posten skapad:
2010-03-22 11:42
Posten ändrad:
2016-07-26 10:54

Visa i Endnote-format

Göteborgs universitet • Tel. 031-786 0000
© Göteborgs universitet 2007