Asymptotic behavior of the expected optimal value of the multidimensional assignment problem

• 成果类型: Article
• 署名作者: Krokhmal, Pavlo A.; Grundel, Don A.; Pardalos, Panos M.
• 署名单位: University of Iowa; United States Department of Defense; United States Air Force; State University System of Florida; University of Florida
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0036-x
• 发表日期: 2007
• 页码: 525-551
• 关键词: 3-index assignment; limit

摘要

The Multidimensional Assignment Problem (MAP) is a higher-dimensional version of the Linear Assignment Problem that arises in the areas of data association, target tracking, resource allocation, etc. This paper elucidates the question of asymptotical behavior of the expected optimal value of the large-scale MAP whose assignment costs are independent identically distributed random variables with a prescribed probability distribution. We demonstrate that for a broad class of continuous distributions the limiting value of the expected optimal cost of the MAP is determined by the location of the left endpoint of the support set of the distribution, and construct asymptotical bounds for the expected optimal cost.