Original scientific paper

Three Algorithms for a Class of Multidimensional Assignment Problems

A. B. Poore ; Department of Mathematics, Colorado State University, Fort Collins, U.S.A.
N. Rijavec ; Department of Mathematics, Colorado State University, Fort Collins, U.S.A.

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.

Keywords

Multitarget tracking; multi-dimensional assignment problems; data association; Lagrangian relaxation; Greedy; Branch; Bound

Hrčak ID:

150478

URI

https://hrcak.srce.hr/150478

Publication date:

30.3.1994.

Visits: 1.041 *