Exact Expectations and Distributions for the Random Assignment Problem

A generalization of the random assignment problem asks the expected cost of the minimum-cost matching of cardinality k in a complete bipartite graph K_mn , with independent random edge weights. With weights drawn from the exponential (1) distribution, the answer has been conjectured to be
S i,j> 0, i+j<k 1/(m-i)(n-j).

Here we prove the conjecture for k< 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 variances in these cases, and conjecture that with k=m=n t (infinity), the variance is 2/n+O(log n/n²). We also include some asymptotic properties of the expectation and variance when k is fixed.