On the number of local minima for the multidimensional assignment problem

Don A. Grundel (), Pavlo A. Krokhmal (), Carlos A. S. Oliveira () and Panos M. Pardalos ()
Additional contact information
Don A. Grundel: Air Armament Center, Eglin AFB
Pavlo A. Krokhmal: The University of Iowa
Carlos A. S. Oliveira: Oklahoma State University
Panos M. Pardalos: University of Florida

Journal of Combinatorial Optimization, 2007, vol. 13, issue 1, No 1, 18 pages

Abstract: Abstract The Multidimensional Assignment Problem (MAP) is an NP-hard combinatorial optimization problem occurring in many applications, such as data association, target tracking, and resource planning. As many solution approaches to this problem rely, at least partly, on local neighborhood search algorithms, the number of local minima affects solution difficulty for these algorithms. This paper investigates the expected number of local minima in randomly generated instances of the MAP. Lower and upper bounds are developed for the expected number of local minima, E[M], in an MAP with iid standard normal coefficients. In a special case of the MAP, a closed-form expression for E[M] is obtained when costs are iid continuous random variables. These results imply that the expected number of local minima is exponential in the number of dimensions of the MAP. Our numerical experiments indicate that larger numbers of local minima have a statistically significant negative effect on the quality of solutions produced by several heuristic algorithms that involve local neighborhood search.

Keywords: Multidimensional assignment problem; Random costs; Combinatorial optimization; Local minima; Neighborhood search (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-9009-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:13:y:2007:i:1:d:10.1007_s10878-006-9009-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-006-9009-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().