Asymptotic behavior of the expected optimal value of the multidimensional assignment problem (Q868473): Difference between revisions

The multidimensional assignment problem is a generalisation of the linear assignment problem. It is to find \(n\) \(d\)-tupels from \(d\) sets of cardinality \(n\) so as to minimize the total cost of the tupels. In this paper the asymptotic behaviour of the expected optimal value \(Z_{d,n}^*\) of the multidimensional assignment problem is studied when the assignment costs are independent identically distributed random variables with an absolutely continuous distribution \(F\) with existing first moment. The main result is that for \(d\geq 3\), \(n\geq 2\) and \((a, b)\) the (finite or infinite) interior of the support set of \(F\) then \(Z_{d,n}^* \to na\) as \(n\to \infty\) or \(d \to \infty\), if some other conditions are satisfied. Furthermore, the authors prove asymptotic bounds on the value of \(Z_{d,n}^*\) and and present some numerical experiments for exponential and uniform distributions of costs.