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 dN 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 ≥ 3. 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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Greedy and $K$-Greedy Algorithms for Multidimensional Data Association


    Contributors:
    Perea, F. (author) / De Waard, H. W. (author)


    Publication date :

    2011-07-01


    Size :

    716616 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Explorer gets greedy

    Online Contents | 2005


    Routenoptimierung mit Greedy-Algorithmen

    Hillert, Freimut | SLUB | 1992


    Greedy adaptive Fano coding

    Rueda, L.G. / Oommen, B.J. | IEEE | 2002


    Greedy Genetic Algorithms, Optimizing Mutations and Bus Driver Scheduling

    Clement, R. / Wren, A. / University of Lisbon et al. | British Library Conference Proceedings | 1995


    Greedy Algorithms for Information Dissemination within Groups of Autonomous Vehicles

    Llatser, Ignacio / Kühlmorgen, Sebastian / Festag, Andreas et al. | British Library Conference Proceedings | 2015