This paper proposes a new algorithm, the Neighborly algorithm, for solving the assignment problem. The new algorithm achieves much better results than the Greedy algorithm while still running in order N log2 (N). The most efficient algorithm to optimally solve the assignment problem, the JVC algorithm, requires order $\mathbf{N}^{\wedge}3$ operations. However, the Greedy algorithm is still in wide use today by target tracking algorithm practitioners due to its speed. The biggest problem with the Greedy algorithm is that the algorithm makes irrevocable, short sighted, assignments without regard to the global optimal solution. To overcome this weakness the Greedy algorithm is modified by incorporating some of the steps used by the Auction algorithm. To the author's knowledge, no new sub-optimal algorithms for solving the assignment problem have been proposed in recent years. Simulation results for the Neighborly algorithm compare favorably to optimal algorithms in the sparse target environment, but perform poorly, as expected, in very dense target environments. In both sparse and dense target environments, the Neighborly algorithm outperforms the Greedy algorithm in both computational efficiency and assignment results.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Don't be Greedy, be Neighborly, a new assignment algorithm


    Beteiligte:
    O'Leary, Bryan (Autor:in)


    Erscheinungsdatum :

    01.03.2019


    Format / Umfang :

    820425 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    A Greedy Path-Based Algorithm for Traffic Assignment

    Xie, Jun / Nie, Yu (Marco) / Liu, Xiaobo | Transportation Research Record | 2018


    Multi-pedestrian Assignment and Detection Based on DE-Greedy Algorithm

    Liu, Mengge / Liu, Zhenghua / Cao, Ziqi et al. | Springer Verlag | 2021


    Multi-pedestrian Assignment and Detection Based on DE-Greedy Algorithm

    Liu, Mengge / Liu, Zhenghua / Cao, Ziqi et al. | TIBKAT | 2022


    Multi-pedestrian Assignment and Detection Based on DE-Greedy Algorithm

    Liu, Mengge / Liu, Zhenghua / Cao, Ziqi et al. | British Library Conference Proceedings | 2022


    Particle Swarm Optimization/Greedy-Search Algorithm for Helicopter Mission Assignment in Disaster Relief

    Andreeva-Mori, Adriana / Kobayashi, Keiji / Shindo, Masato | AIAA | 2015