Exact expectations and distributions for the random assignment problem
by
Sven Erick Alm and Gregory B. Sorkin
Uppsala University and IBM T.J. Watson Research Center
U.U.D.M. Report 1999:27 ISSN 1101-3591
In Combinatorics, Probablity and Computing 11 (2202), 217-248.
Postscript
Abstract
A generalization of the random assignment problem
asks the expected cost of the
minimum-cost matching of cardinality $k$ in a complete bipartite
graph $\Kmn$,
with independent random edge weights.
With weights drawn from the exponential(1) distribution,
the answer has been conjectured to be
$\sum_{ i,j \ge 0 , \ i+j < k } \frac{1}{(m-i)(n-j)}$.
Here, we prove the conjecture for
$k \leq 4$, $k=m=5$, and $k=m=n=6$,
using a structured, automated proof technique that results in
proofs with relatively few cases.
The method yields not only the minimum assignment cost's expectation
but the Laplace transform of its distribution as well.
From the Laplace transform we compute the variance in these cases,
and conjecture that with $k=m=n \ra \infty$, the variance
is $2/n + O(\log n / n^2)$.
We also include some asymptotic properties of the expectation
and variance when $k$ is fixed.