| 1. |
- Hessler, Martin, 1979-, et al.
(författare)
-
Concentration of the cost of a random matching problem
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- Let Mn be the minimum cost of a perfect matching on a complete graph on n vertices whose edges are assigned independent exponential costs. It follows from work of D. Aldous that Mn converges in probability to π2/12. This was earlier conjectured by M. Mézard and G. Parisi. We establish the more precise result that E | Mn – π2/12| = O(n-1/2).
|
|
| 2. |
- Hessler, Martin, 1979-, et al.
(författare)
-
LP-relaxed matching with zero-cost loops
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We study a certain LP-relaxation of the minimum matching problem on a complete graph with random edge costs. In earlier work by Wästlund it was shown that the expected cost of the optimum solution has the simple form 1 – 1/4 + 1/9 – ··· ± 1/n2, an analogue of a corresponding formula for the bipartite problem. Wegeneralize by conditioning on certain edges having zero cost. It is proved that if each node independently is given a zero-cost loop with probability 1 ¡ p then the expected cost of the optimum solution is p – p2/4 + p3/9 – ··· ± pn/n2.
|
|
| 3. |
- Hessler, Martin, 1979-, et al.
(författare)
-
The polymatroid assignment problem
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- In 1998 G. Parisi published the two page note, with the conjecturedexact formula for the random bipartite matching (or assignment) problemwith exponential edge costs. This formula was subsequently proved and generalized in different directions. One such generalization given in was called the flow problem. Here we take the generalization process one step further. In a two-dimensional urn-processwas developed in order to calculate all moments of the cost of the flow problem. This process is here generalized to a larger class of optimization problems on the bipartite graph. These problems are defined by assigning a polymatroid structure to each of the two sets of vertices. An edge set isa feasible solution to the optimization problem if the two associated vertex(multi-)sets are both independent. Our main theorem states that the moments of the cost of the polymatroid assignment problem are characterizedby the associated urn process. We apply this theorem to some concrete problems which are not covered by previously known generalization of the bipartite matching problem.
|
|
| 4. |
- Larsson, Urban, 1965, et al.
(författare)
-
Maharaja Nim : Wythoff's Queen meets the Knight
- 2013
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We relax the hypothesis of a recent result of A. S. Fraenkel and U. Peled on certain complementary sequences of positive integers. The motivation is to understand to asymptotic behavior of the impartial game of \emph{Maharaja Nim}, an extension of the classical game of Wythoff Nim. In the latter game, two players take turn in moving a single Queen of Chess on a large board, attempting to be the first to put her in the lower left corner, position $(0,0)$. Here, in addition to the classical rules, a player may also move the Queen as the Knight of Chess moves, still taking into consideration that, by moving no coordinate increases. We prove that the second player's winning positions are close to those of Wythoff Nim, namely they are within a bounded distance to the half-lines, starting at the origin, of slope $\frac{\sqrt{5}+1}{2}$ and $\frac{\sqrt{5}-1}{2}$ respectively. We encode the patterns of the P-positions by means of a certain \emph{dictionary process}, thus introducing a new method for analyzing games related to Wythoff Nim. Via Post's Tag productions, we also prove that, in general, such dictionary processes are algorithmically undecidable.
|
|
