| 1. |
- Hessler, Martin, 1979-, et al.
(author)
-
Concentration of the cost of a random matching problem
-
Other publication (other academic/artistic)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, et al.
(author)
-
Edge cover and polymatroid flow problems
- 2010
-
In: Electronic Journal of Probability. - : Institute of Mathematical Statistics. - 1083-6489. ; 15, s. 2200-2219
-
Journal article (peer-reviewed)abstract
- In an n by n complete bipartite graph with independent exponentially distributed edge costs, we ask for the minimum total cost of a set of edges of which each vertex is incident to at least one. This so-called minimum edge cover problem is a relaxation of perfect matching. We show that the large n limit cost of the minimum edge cover is W(1)(2) + 2W(1) approximate to 1.456, where W is the Lambert W-function. In particular this means that the minimum edge cover is essentially cheaper than the minimum perfect matching, whose limit cost is pi(2)/6 approximate to 1.645. We obtain this result through a generalization of the perfect matching problem to a setting where we impose a (poly-)matroid structure on the two vertex-sets of the graph, and ask for an edge set of prescribed size connecting independent sets.
|
|
| 3. |
- Hessler, Martin, 1979-, et al.
(author)
-
LP-relaxed matching with zero-cost loops
-
Other publication (other academic/artistic)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-
(author)
-
Optimization, Matroids and Error-Correcting Codes
- 2009
-
Doctoral thesis (other academic/artistic)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.
(author)
-
The polymatroid assignment problem
-
Other publication (other academic/artistic)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.
|
|
