Multidimensional assignment: applications and some thoughts
Dept. of Applied Statistics, Operations Research and Quality
Polytechnic University of Valencia
This paper reviews the multi dimensional assignment problem (MAP) and some of its applications. The MAP is a higher dimensional version of the classic two-sided assignment problem, and has applications in areas such as target tracking and robot vision. These applications are reviewed as well as the game arising from the MAP, called the m-sided assignment game (m-SAG). Some thoughts about the use of approximation algorithms in m-SAG to avoid the NP-hardness of the underlying MAP are described. The paper ﬁnishes with a brief introduction to the concept of approximation games. The characteristic function of these games cannot be calculated and is, therefore, approximated.
- Keywords: Multidimensional assignment, Tracking, Games, Approximation
- AMS Subject classifications: 90B80, 91A46.