11. |
|
|
12. |
- Wästlund, Johan, 1971
(författare)
-
Replica symmetry of the minimum matching
- 2012
-
Ingår i: Annals of Mathematics. - : Annals of Mathematics. - 0003-486X. ; 175:3, s. 1061-1091
-
Tidskriftsartikel (refereegranskat)abstract
- We establish the soundness of the replica symmetric ansatz introduced by M. Mezard and G. Parisi for the minimum matching problem in the pseudo-dimension d mean field model for d >= 1. The case d = 1 corresponds to the pi(2)/6-limit for the assignment problem proved by D. Aldous in 2001. We introduce a game-theoretical framework by which we establish the analogous limit also for d > 1.
|
|
13. |
- Wästlund, Johan, 1971
(författare)
-
The Blind Passenger and the Assignment Problem
- 2011
-
Ingår i: Combinatorics Probability & Computing. - : Cambridge University Press (CUP). - 0963-5483 .- 1469-2163. ; 20:3, s. 467-480
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce a discrete random process which we call the passenger model, and show that it is connected to a certain random model of the assignment problem and in particular to the so-called Buck-Chan-Robbins urn process. We propose a conjecture on the distribution of the location of the minimum cost assignment in a cost matrix with zeros at specified positions and remaining entries of exponential distribution. The conjecture is consistent with earlier results on the participation probability of an individual matrix entry. We also use the passenger model to verify a conjecture by V. Dotsenko on the assignment problem.
|
|
14. |
- Wästlund, Johan, 1971
(författare)
-
The mean field traveling salesman and related problems
- 2010
-
Ingår i: Acta Mathematica. - : International Press of Boston. - 0001-5962. ; 204:1, s. 91-150
-
Tidskriftsartikel (refereegranskat)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.
|
|