|
 |
|
|
| Abstract: |
|
|
|
The multidimensional assignment problem (MAP) is a combinatorial problem |
|
|
|
where elements of a variable number of sets must be matched, in order to find a |
|
|
|
minimum cost solution. The MAP has applications in a large number of areas, and is |
|
|
| known to be NP-hard. We survey some of the recent work being done in the letermination |
|
|
| of the asymptotic value of optimal solutions to the MAP, when costs are drawn from a |
|
|
|
known distribution (e.g., exponential, uniform, or normal). Novel results, concerning the |
|
|
| average number of local minima for random instances of the MAP for random distributions |
|
|
are discussed. We also present computational experiments with local and global search |
|
|
| algorithms that illustrate the validity of our results. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
