Submitted to IEEE Trans. on Aerospace and Electronic Systems.
Optimizing Murty's Ranked Assignment Method
Matt L. Miller
P.O. Box 964 ARP-3
Harold S. Stone and Ingemar J. Cox
NEC Research Institute
4 Independence Way
Princeton, NJ 08540
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 multi-target tracking, where it has been shown that real-time multi-target tracking is now feasible, but many other uses of the algorithm are also possible. 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 ? 100 assignment problems, these optimizations produce a speedup of over a factor of 20, finding all 100 solutions in about :6 seconds. For a random cost matrix, the average time complexity for finding k solutions to random N ?N problems appears to be nearly linear in both k and N , for sufficiently large k.
In earlier work [CM95], we showed that the k-best hypotheses of Reid's multiple hypothesis tracking algorithm (MHT) [Rei79] could be efficiently generated in O(N4) worst case time using an algorithm due to Murty [Mur68]. In a companion paper to this, we compared Murty's algorithm to that of Danchick and Newnam [DN93] and showed that real-time multi-target tracking is now feasible in some circumstances. In this paper, we describe three optimizations to the original algorithm of Murty that improve performance by several orders of magnitude when applied to a large collection of randomly generated problems. These optimizations are useful to any application in which a ranked set of assignments is need.
Gabow [Gab78] has also studied the complexity of finding the k-best solutions. He showed a complexity bound for finding the kth best matching for a bipartite graph with N nodes and M arcs to be O(k min(N3; MN log N )). This bounds the worst-case time. In contrast, our approach yields a much lower complexity because we measure the expected time rather than the worst-case time. The measured complexity tends to grow quadratically in N rather than cubicly in N for dense random graphs.
Section 2 begins with a brief description of Murty's algorithm and is followed by a discussion of key properties of the Jonker and Volgenant algorithm for finding the least-cost assignment in Section 3. Section 4 then describes the three optimizations we employed in the implementation of Murty's algorithm. The first optimization, inheriting dual variables and partial solutions during partitioning, is a well known technique [BM71] which reduces the worst case time of Murty's algorithm from O(kN4) to O(kN3). The second