| 51. |
- Wästlund, Johan
(author)
-
Perfect packings of squares using the stack-pack strategy
- 2003
-
In: Discrete & Computational Geometry. - : Springer Science and Business Media LLC. - 0179-5376 .- 1432-0444. ; 29:4, s. 625-631
-
Journal article (peer-reviewed)abstract
- We consider the problem of packing an infinite set of square tiles into a finite number of rectangular boxes. We introduce a simple packing strategy that we call stack-pack. Using this strategy, we prove that if 1/2 < t < 2/3, then the squares of side n-t, for positive integers n, can be packed into some finite collection of square boxes of the same area ? (2r) as the total area of the tiles.
|
|
| 52. |
- Wästlund, Johan, 1971-
(author)
-
Random Assignment Problems
- 2003
-
In: Random Structures and Algorithms,2003.
-
Conference paper (other academic/artistic)
|
|
| 53. |
- Wästlund, Johan, 1971
(author)
-
Random matching problems on the complete graph
- 2008
-
In: Electronic Communications in Probability. - 1083-589X. ; 13, s. 258-265
-
Journal article (peer-reviewed)abstract
- The edges of the complete graph on n vertices are assigned independent exponentially dis- tributed costs. A k-matching is a set of k edges of which no two have a vertex in common. We obtain explicit bounds on the expected value of the minimum total cost Ck,n of a k-matching. In particular we prove that if n = 2k then π2 /12 < ECk,n < π2 /12 + log n/n.
|
|
| 54. |
- Wästlund, Johan, 1971
(author)
-
Replica symmetry of the minimum matching
- 2012
-
In: Annals of Mathematics. - : Annals of Mathematics. - 0003-486X. ; 175:3, s. 1061-1091
-
Journal article (peer-reviewed)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.
|
|
| 55. |
- Wästlund, Johan, 1971
(author)
-
The Blind Passenger and the Assignment Problem
- 2011
-
In: Combinatorics Probability & Computing. - : Cambridge University Press (CUP). - 0963-5483 .- 1469-2163. ; 20:3, s. 467-480
-
Journal article (peer-reviewed)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.
|
|
| 56. |
- Wästlund, Johan, 1971
(author)
-
The mean field traveling salesman and related problems
- 2010
-
In: Acta Mathematica. - : International Press of Boston. - 0001-5962. ; 204:1, s. 91-150
-
Journal article (peer-reviewed)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.
|
|
| 57. |
- Wästlund, Johan
(author)
-
The variance and higher moments in the random assignment problem
- 2005
-
Reports (other academic/artistic)abstract
- We obtain exact formulas for all moments of the cost Cn of the inimum assignment in the complete bipartite graph Kn,n with independent exp(1) edge costs. In particular we prove that as n tends to infinity, the variance of Cn is c/n+O(1/n2), where c = 4ζ(2)-4ζ(3), or approximately 1.7715.
|
|
| 58. |
- Wästlund, Johan
(author)
-
Two-person symmetric whist
- 2005
-
Reports (other academic/artistic)abstract
- The game of two-person whist is played with a deck of cards. Each card belongs to a suit, and each suit is totally ordered. The cards are distributed between the two players so that each player receives the same number of cards. Hence both players have complete information about the deal. Play proceeds in tricks, with the obligation to follow suit, as in many real-world card games.We study the symmetric case of this game, that is, we assume that in each suit, the two players have the same number of cards. Under this assumption, the second player in each trick will always be able to follow suit.We show how to assign a value from a certain semigroup to each single-suit card distribution in such a way that the outcome of a multisuit deal under optimal play is determined by the sum of the values of the individual suit. This allows us to play a deal perfectly, provided that we can compute the values of its single-suit components. Although we do not have an efficient algorithm for doing this in general, we give methods that will allow us to find the value of a suit quickly in most cases.We also establish certain general facts about the game, for instance the nontrivial fact that a higher card is always at least as good as a smaller card in the same suit.
|
|
| 59. |
- Wästlund, Johan, 1971-
(author)
-
Two-person symmetric whist
- 2005
-
In: The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 12:1, s. R44-
-
Journal article (peer-reviewed)abstract
- We introduce a two-person perfect information model of trick taking games. A set of cards is distributed between two players, and play proceeds in tricks with the obligation to follow suit, as in many real-world card games. We assume that in each suit, the two players have the same number of cards. Under this assumption, we show how to assign a value from a certain semigroup to each single-suit card distribution in such a way that the outcome of a multi-suit deal under optimal play is determined by the sum of the values of the individual suits.
|
|
