期刊
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
卷 122, 期 3, 页码 487-500出版社
SPRINGER/PLENUM PUBLISHERS
DOI: 10.1023/B:JOTA.0000042592.16418.1b
关键词
multidimensional assignment problem; combinatorial optimization; asymptotic results
The multidimensional assignment problem ( MAP) is an NP-hard combinatorial optimization problem occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables. We prove also that the mean optimal solution goes to negative infinity when assignment costs are independent normally distributed random variables.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据