Optimizing Murty's ranked assignment method

View Researcher's Other Codes

Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).

Please contact us in case of a broken link from here

Authors M. Miller, H. Stone, I. Cox
Journal/Conference Name IEEE Transactions on Aerospace and Electronic Systems
Paper Category
Paper Abstract 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.
Date of publication 1997
Code Programming Language Python
Comment

Copyright Researcher 2021