Izvorni znanstveni članak
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.
Sažetak
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.
Ključne riječi
Multitarget tracking; multi-dimensional assignment problems; data association; Lagrangian relaxation; Greedy; Branch; Bound
Hrčak ID:
150478
URI
Datum izdavanja:
30.3.1994.
Posjeta: 1.060 *