Optimizing Murty's ranked assignment method
- 1 July 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Aerospace and Electronic Systems
- Vol. 33 (3), 851-862
- https://doi.org/10.1109/7.599256
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.Keywords
This publication has 8 references indexed in Scilit:
- A new algorithm for the generalized multidimensional assignment problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A comparison of two algorithms for determining ranked assignments with application to multitarget tracking and motion correspondenceIEEE Transactions on Aerospace and Electronic Systems, 1997
- A fast method for finding the exact N-best hypotheses for multitarget trackingIEEE Transactions on Aerospace and Electronic Systems, 1993
- A shortest augmenting path algorithm for dense and sparse linear assignment problemsComputing, 1987
- An algorithm for tracking multiple targetsIEEE Transactions on Automatic Control, 1979
- Pathology of Traveling-Salesman Subtour-Elimination AlgorithmsOperations Research, 1971
- Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing CostOperations Research, 1968
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955