
Submitted to IEEE Trans. on Aerospace and Electronic Systems.
Optimizing Murty's Ranked Assignment Method
Matt L. Miller
Baltic Images
P.O. Box 964 ARP3
2300 Vilnius
LITHUANIA
mlm@bimage.tipas.lt.ee
Harold S. Stone and Ingemar J. Cox
NEC Research Institute
4 Independence Way
Princeton, NJ 08540
U.S.A.
hstoneingemar@research.nj.nec.com
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 realtime multitarget 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.
1 Introduction
In earlier work [CM95], we showed that the kbest 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 realtime multitarget 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 kbest 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 worstcase time. In contrast, our approach yields a much lower complexity because we measure the expected time rather than the worstcase 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 leastcost 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