No label defined (Q3147236)

Let \(A\) be an \(m\times n\) matrix whose elements are i.i.d. random variables distributed exponentially with parameter 1. Let \(A^*= A^*(k,m,n)\) be the smallest sum of \(k\) elements of \(A\) where no two of them share a row or column, i.e. \(A^*\) is the cost of the minimum \(k\)-assignment of \(A\). For \(k= m= n\) we have the classical assignment problem. The authors study the conjecture \[ f(k,m,n)= EA^*= \sum_{i+ j< k}(m- i)^{-1}(n- j)^{-1}\tag{1} \] and related problems. For the classical problem this implies the conjecture \(f(n,n,n)= \sum_{i\leq n} i^2\). One also may see \(A^*\) as the minimum-cost cardinality-\(k\) matching in the complete bipartite graph \(K_{mn}\). A linear programming formulation is also given. The authors generalize this setting by allowing a set \(Z\subset K_{mn}\) with \(a(i,j)= 0\). Their main theorem, with the obvious definition of \(A^*(k,m,n,Z)\) runs as follows: Let there be \(R\subset K_{mn}\) such that \(R\cap Z=\emptyset\), \(| R\cap M|= s\) fixed for all matchings \(M\) in a certain class of matchings. Then \(A^*(k,m,n,Z)\) is distributed as \(A^*(k,m,n,Z\cup \{(i,j)\})\) plus an independent exponential. Here \((i,j)\) is chosen at random from \(R\). This promises a recurrence. By a dynamic programming algorithm, using this theorem, \(f(k,m,n)\) and \(\psi(k,m,n,t)= E(- t\exp(A^*(k,m,n)))\) are computed for \((k,m,n)= (2,3,3)\), \((3,4,4)\), \((4,5,5)\), \((5,5,6)\) and \((6,6,6)\), verifying (1). Section 5.5 describes a procedure to ``lift'' \(m\) and \(n\). In this way (1) is proved for \(k\leq 4\), \(m,n\geq k\) and for \(k= m= 5\), \(n\geq 5\). Further proofs are restricted by the misfortune that the above set \(R\) does not always exist. For the study of \(V(k,m,n)= \text{Var\,}A^*\) the authors define \(S(k,m,n,t)\) as a quotient of two products of Laplace transforms of exponentials. It is shown that \(S\) is the Laplace transform of a probability distribution whose expectation equals (1). Also \(S\) approximates but does not equal \(\psi\). It is conjectured that \(V(k,m,n)\) is equal to the variance corresponding to \(S\). Finally, the asymptotic behaviour and bounds of \(f(k,m,n)\) and \(V(k,m,n)\) are studied. In particular: \(nV(n,n,n)\geq 1\).