next up previous contents index
Next: 9.8.2 The Sequential Algorithm Up: 9.8 Munkres Algorithm for Previous: 9.8 Munkres Algorithm for

9.8.1 Introduction

The so-called assignment problem  is of considerable importance in a variety of applications, and can be stated as follows. Let


be two sets of items, and let


be a measure of the distance (dissimilarity) between individual items from the two lists. Taking , the objective of the assignment problem is to find the particular mapping


such that the total association score


is minimized over all permutations .

For , the naive (exhaustive search) complexity of the assignment problem is . There are, however, a variety of exact solutions to the assignment problem with reduced complexity ([Blackman:86a], [Burgeios:71a], [Kuhn:55a]). Section 9.8.2 briefly describes one such method, Munkres algorithm  [Kuhn:55a], and presents a particular sequential implementation. Performance of the algorithm is examined for the particularly nasty problem of associating lists of random points within the unit square. In Section 9.8.3, the algorithm is generalized for concurrent execution, and performance results for runs on the Mark III hypercube are presented.

Guy Robinson
Wed Mar 1 10:19:35 EST 1995