Asymptotic Results for Random Multidimensional Assignment Problems

The multidimensional assignment problem (MAP) is an NP-hard combinatorial optimization problem occurring in applications such as data association and target tracking. In this paper, we investigate characteristics of the mean optimal solution values for random MAPs with axial constraints. Throughout the study, we consider cost coefficients taken from three different random distributions: uniform, exponential and standard normal. In the cases of uniform and exponential costs, experimental data indicates that the mean optimal value converges to zero when the problem size increases. We give a short proof of this result for the case of exponentially distributed costs when the number of elements in each dimension is restricted to two. In the case of standard normal costs, experimental data indicates the mean optimal value goes to negative infinity with increasing problem size. Using curve fitting techniques, we develop numerical estimates of the mean optimal value for various sized problems. The experiments indicate that numerical estimates are quite accurate in predicting the optimal solution value of a random instance of the MAP.