Title :
A new class of Heuristic Polynomial Time Algorithms to solve the Multidimensional Assignment Problem
Author :
Perea, F. ; de Waard, H.W.
Author_Institution :
AWS Dept., Thales Naval Nederland B.V.
Abstract :
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in many applications, for instance in multi-target multi-sensor tracking problems. It is well-known that the MAP is NP-hard. The objective of a MAP is to match d-tuples of objects in such a way that the solution with the optimum total cost is found. In this paper a new class of approximation algorithms to solve the MAP is presented, named K-SGTS, and its effectiveness in multi-target multi-sensor tracking situations is shown. Its computational complexity is proven to be polynomial. Experimental results on the accuracy and speed of K-SGTS are provided in the last section of the paper
Keywords :
approximation theory; sensor fusion; target tracking; K-SGTS algorithm; MAP; approximation algorithm; combinatorial optimization; heuristic polynomial time algorithm; multidimensional assignment problem; multitarget multisensor tracking; semigreedy track selection algorithm; Clutter; Covariance matrix; Heuristic algorithms; Multidimensional systems; Polynomials; Position measurement; Radar measurements; Radar tracking; State estimation; Target tracking; Tracking; data association; operations research;
Conference_Titel :
Information Fusion, 2006 9th International Conference on
Conference_Location :
Florence
Print_ISBN :
1-4244-0953-5
Electronic_ISBN :
0-9721844-6-5
DOI :
10.1109/ICIF.2006.301641
