6533b82dfe1ef96bd12909d7

RESEARCH PRODUCT

Greedy and K-Greedy algoritmhs for multidimensional data association

H. W. De WaardFederico Perea

subject

OptimizationMathematical optimizationCombinatorial optimizationPolynomial approximationESTADISTICA E INVESTIGACION OPERATIVAAerospace EngineeringApproximation algorithmNP-hardSensor fusionDimension (vector space)Combinatorial optimization problemsMulti-target trackingPolynomial time heuristicsCombinatorial optimizationAlgorithm designElectrical and Electronic EngineeringMultidimensional assignmentObjective functionsHeuristicsGreedy algorithmTime complexityAlgorithmMultidimensional dataAlgorithmsMathematics

description

[EN] The multidimensional assignment (MDA) problem is a combinatorial optimization problem arising in many applications, for instance multitarget tracking (MTT). The objective of an MDA problem of dimension $d\in\Bbb{N}$ is to match groups of $d$ objects in such a way that each measurement is associated with at most one track and each track is associated with at most one measurement from each list, optimizing a certain objective function. It is well known that the MDA problem is NP-hard for $d\geq3$. In this paper five new polynomial time heuristics to solve the MDA problem arising in MTT are presented. They are all based on the semi-greedy approach introduced in earlier research. Experimental results on the accuracy and speed of the proposed algorithms in MTT problems are provided. © 2006 IEEE.

yearjournalcountryeditionlanguage
2011-07-01
10.13039/501100000780https://dx.doi.org/10.1109/TAES.2011.5937273