| 1. |
|
|
| 2. |
- 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).
|
|
| 3. |
- 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.
|
|
| 4. |
- Hessler, Martin, 1978-
(författare)
-
Optimization, Matroids and Error-Correcting Codes
- 2009
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The first subject we investigate in this thesis deals with optimization problems on graphs. The edges are given costs defined by the values of independent exponential random variables. We show how to calculate some or all moments of the distributions of the costs of some optimization problems on graphs.The second subject that we investigate is 1-error correcting perfect binary codes, perfect codes for short. In most work about perfect codes, two codes are considered equivalent if there is an isometric mapping between them. We call this isometric equivalence. Another type of equivalence is given if two codes can be mapped on each other using a non-singular linear map. We call this linear equivalence. A third type of equivalence is given if two codes can be mapped on each other using a composition of an isometric map and a non-singular linear map. We call this extended equivalence.In Paper 1 we give a new better bound on how much the cost of the matching problem with exponential edge costs varies from its mean.In Paper 2 we calculate the expected cost of an LP-relaxed version of the matching problem where some edges are given zero cost. A special case is when the vertices with probability 1 – p have a zero cost loop, for this problem we prove that the expected cost is given by a formula.In Paper 3 we define the polymatroid assignment problem and give a formula for calculating all moments of its cost.In Paper 4 we present a computer enumeration of the 197 isometric equivalence classes of the perfect codes of length 31 of rank 27 and with a kernel of dimension 24.In Paper 5 we investigate when it is possible to map two perfect codes on each other using a non-singular linear map.In Paper 6 we give an invariant for the equivalence classes of all perfect codes of all lengths when linear equivalence is considered.In Paper 7 we give an invariant for the equivalence classes of all perfect codes of all lengths when extended equivalence is considered.In Paper 8 we define a class of perfect codes that we call FRH-codes. It is shown that each FRH-code is linearly equivalent to a so called Phelps code and that this class contains Phelps codes as a proper subset.
|
|
| 5. |
- 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.
|
|
| 6. |
- Högberg, Johan, 1973-
(författare)
-
Gameful experiences : The not so painful road to gainful behavior
- 2019
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The aim of this work is to investigate the experiences that users make when using gamified services and the effect that such experiences have on the targeted behavioral outcomes. Considerable attention is dedicated to the gameful experience, since this experience is necessary for gamification to affect the target behavior. Moreover, the effectiveness of gamification at triggering different motivational mechanisms and the role of engagement is investigated.This dissertation contains three papers. Paper 1 uses a mixed-methods approach to develop a model and a measure of the gameful experience. Paper 2 uses a field experimental approach to investigate the effect of gamification on a decision to use offers in a store, and the role of engagement for this effect to occur. Finally, Paper 3 uses a field experiment to investigate the contribution of gamification to value creation in stores and how such value creation relates to brand engagement.The first main finding is a model of the gameful experience that includes the dimensions of accomplishment, challenge, competition, guided, immersion, playfulness, and social experience, and the instrument for measuring this experience. The second main finding is that challenge-based gamification can induce positive affect, which can influence evaluative judgments (thus utilizing the affective quality of System 1 to change the target behavior) and, ultimately, brand engagement. However, such challenge-based gamification does not seem to be effective when aiming to affect the biased System 1 through effort justification. The third main finding is the results that indicate that a user needs to be engaged in order for a gamified service to work properly.
|
|
| 7. |
- Janson, Svante, et al.
(författare)
-
Addendum to The Minimal Spanning Tree in a Complete Graph and a Functional Limit Theorem for Trees in a Random Graph
- 2006
-
Ingår i: Random structures & algorithms (Print). - : Wiley. - 1042-9832 .- 1098-2418. ; 28:4, s. 511-512
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- The minimal weight of a spanning tree in a complete graph Kn with independent, uniformly distributed random weights on the edges is shown to have an asymptotic normal distribution. The proof uses a functional limit extension of results by Barbour and Pittel on the distribution of the number of tree components of given sizes in a random graph.
|
|
| 8. |
- 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.
|
|
| 9. |
- Larsson, Urban, 1965, et al.
(författare)
-
Maharaja Nim
- 2013
-
Tidskriftsartikel (ö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.
|
|
| 10. |
|
|
