optimization of Section 4.2 is also straightforward [BM71] and while it does not reduce the worst case performance, the average time is substantially improved. The third optimization, Section 4.3, partitioning in an optimized order, is believed to be novel. Again, the worst case time is unaffected. However, for random cost matrices the average time to find the k-best solutions grew almost linearly in both k and N for our test problems. The performance improvements due to these optimizations are experimentally measured in Section 5. Finally, Section 6 discusses the results and includes additional information relevant to the application of Murty's algorithm to multi-target tracking.

2 A Review of Murty's Algorithm for Finding Ranked Solutions to the Assignment Problem

In order to provide the reader with a background knowledge of Murty's method, we briefly describe the method here. Figure 1 shows pseudocode for Murty's method of finding the k-best solutions to a linear assignment problem, P 0. The problem is expressed as a bipartite graph, represented as a list of triples, < y; z; l >. In a multi-target tracking application, each y represents a hypothesized target, each z represents a measurement, and l is the negative log-likelihood that z is a measurement of y. A solution, S, to such an assignment problem is a list of triples in which each y and each z appears exactly once. The cost of a solution is the sum of the l's in its triples. The k-best solutions are those with the k lowest costs.

The single best solution to P0 can be found using one of the classical methods of solving assignment problems [Kuh55, JV87]. We use Jonker and Volgenant's method [JV87], which has worst-case time O(N3), where N is the number of nodes in the graph. This algorithm will be discussed in the next section. Subsequent solutions to P0 are found by solving a succession of assignment problems that are created from P0 by a process called partitioning".

A problem, P , with best solution S and size n, is partitioned into a set of subproblems, P ; P 1; : : : P n,
such that:

1. The union of the set of possible solutions to P through P n is exactly the set of possible solutions to
P minus the solution S, and

2. The sets of possible solutions to P through P n are disjoint.

To make subproblem P t , we copy P and remove from it the i'th triple in S, < yj; zi; l >. This means that

no solution to P t can contain < yj; zi; l >, so S cannot be a solution to P t . Next, before making subproblems

P t + 1 through P n, we force < yj; zi; l > to be in the solutions to those subproblems. To do so, we remove from P all the triples < yj; zh; l >, h <> i and < yh; zi; l >, h <> j. Every possible solution to this modified

P must contain < yj; zi; l >, so the sets of possible solutions to any subproblem P h, where h > t, will be

disjoint from the set of possible solutions to P t .
We partition P0 according to its best solution, S0, and place the resulting subproblems, together with their best solutions, on a priority queue of problem/solution pairs. We then find the problem P in the