Multidimensional assignment: applications and some thoughts

Federico Perea
Dept. of Applied Statistics, Operations Research and Quality
Polytechnic University of Valencia
This e-mail address is being protected from spam bots, you need JavaScript enabled to view it

  • Abstract
    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.
  • Keywords: Multidimensional assignment, Tracking, Games, Approximation
  • AMS Subject classifications: 90B80, 91A46.