Multidimensional assignment: applications and some thoughts

Federico Perea
Dept. of Applied Statistics, Operations Research and Quality
Polytechnic University of Valencia
Esta dirección de correo electrónico está protegida contra los robots de spam, necesita tener Javascript activado para poder verla

  • 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.