Three Algorithms for a Class of Multidimensional Assignment Problems

Abstract

The assignment problem of matching the elements of two sets at some cost or to some benefit is well known and can be solved in polynomial time. However, many applications, particularly those in remote sensing and computer vision, require matching elements from more than two sets at some cost. Such problems are called multidimensional assignment problems and are known to be NP-hard. For time-critical applications and nontrivial multidimensional assignment problems, fast near-optimal algorithms are the only alternative. This paper compares three such algorithms: greedy, limited branch and bound, and Lagrangian relaxation.