We describe an implementation of an algorithm due to Murty for determining a ranked set of solutions to assignment problems. The intended use of the algorithm is in the context of multitarget tracking, where it has been shown that real-time multitarget tracking is feasible for some problems, but many other uses of the algorithm are also possible. The following three optimizations are discussed: (1) inheriting dual variables and partial solutions during partitioning, (2) sorting subproblems by lower cost bounds before solving, and (3) partitioning in an optimized order. When used to find the 100 best solutions to random 100/spl times/100 assignment problems, these optimizations produce a speedup of over a factor of 20, finding all 100 solutions in about 0.6 s. For a random cost matrix, the average time complexity for finding k solutions to random N/spl times/N problems appears to be nearly linear in both k and N, for sufficiently large k.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Optimizing Murty's ranked assignment method


    Beteiligte:
    Miller, M.L. (Autor:in) / Stone, H.S. (Autor:in) / Cox, I.J. (Autor:in)


    Erscheinungsdatum :

    01.07.1997


    Format / Umfang :

    2297322 byte




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Optimizing Murty's Ranked Assignment Method

    Miller, M.L. | Online Contents | 1997


    Modified Murty's Algorithm for Diverse Multitarget Top Hypothesis Extraction

    Xiaofan He / Tharmarasa, R. / Kirubarajan, T. et al. | IEEE | 2013


    A Graph Neural Network Approach for Solving the Ranked Assignment Problem in Multi-Object Tracking

    Dehler, Robin / Herrmann, Martin / Strohbeck, Jan et al. | IEEE | 2024


    Optimizing the Door Assignment in LTL-Terminals

    Chmielewski, A. / Naujoks, B. / Janas, M. et al. | British Library Online Contents | 2009


    Optimizing the Door Assignment in LTL-Terminals

    Chmielewski, Annette | Online Contents | 2009