Summary: 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 determination 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.