Multidimensional assignment: applications and some thoughts
Federico Perea · BEIO, Boletín de Estadística e Investigación Operativa · 2011
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 finishes with a brief introduction to the concept of approximation games. The characteristic function of these games cannot be calculated and is, therefore, approximated.