CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

The mean field traveling salesman and related problems

Johan Wästlund (Institutionen för matematiska vetenskaper, matematik)
Acta Mathematica (0001-5962). Vol. 204 (2010), 1, p. 91-150.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: random assignment problem, expected value, combinatorial optimization, statistical-mechanics, minimum assignment, exact expectations, finite-size, spin-glass, model, asymptotics



Denna post skapades 2010-03-22. Senast ändrad 2016-07-26.
CPL Pubid: 118214

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)

Ämnesområden

Matematik

Chalmers infrastruktur