The input to the assignment problem is the matrix 
of dissimilarities from Equation 9.19. The first point to note
is that the particular assignment which minimizes Equation 9.21
is not altered if a fixed value is added to or subtracted from all
entries in any row or column of the cost matrix D. Exploiting this fact,
Munkres' solution to the assignment problem can be divided into two parts
denoting the row indices of all zeros in
column i, construction of a so-called minimal representative set,
meaning a distinct selection 
for each i, such that
.
The preceding paragraph provides a hopelessly incomplete hint as to the
number theoretic basis for Munkres algorithm. The particular implementation
of Munkres algorithm used in this work is as described in Chapter 14 of
[Blackman:86a]. To be definite, take 
and let the
columns of the distance matrix be associated with items from list 
.
The first step is to subtract the smallest item in each column from all
entries in the column. The rest of the algorithm can be viewed as a search
for special zero entries (starred zeros 
), and proceeds as
follows:
Munkres Algorithm
Count, Solution Assessment
.
entries in the matrix provide the solution to
the assignment problem.
. If no such zero exists, go to Step 5
exists in the row of the 
, go to Step 4.
exists, cover this row and uncover the column of
the 
. Return to Step 3.1 to find a new Z.
: Unpaired 
from Step 3.2
: The 
in the column of 
: The 
in the row of 
,
if such a zero exists
: The 
in the column of 
for some N.
The preceding algorithm involves flags (starred or primed) associated with
zero entries in the distance matrix, as well as ``covered'' tags associated
with individual rows and columns. The implementation of the zero tagging is
done by first noting that there is at most one 
or 
in any row or column. The covers and zero tags of the algorithm are
accordingly implemented using five simple arrays:
:
.
:
:
locators for columns of the matrix. If positive,
ZS
is the row index of the 
in the 
column of the matrix.
:
locators for rows of the matrix. If positive,
ZR
is the column of the 
in the 
row of the matrix.
:
locators for rows of the matrix. If positive,
ZP
is the column of the 
in the 
row of the matrix.
Figure 9.19: Flowchart for Munkres Algorithm
Entries in the cover arrays CC and CR are one if the row or column is covered zero otherwise. Entries in the zero-locator arrays ZS, ZR, and ZP are zero if no zero of the appropriate type exists in the indexed row or column.
With the star-prime-cover scheme of the preceding paragraph, a sequential implementation of Munkres algorithm is completely straightforward. At the beginning of Step 1, all cover and locator flags are set to zero, and the initial zero search provides an initial set of nonzero entries in ZS(). Step 2 sets appropriate entries in CC() to one and simply counts the covered columns. Steps 3 and 5 are trivially implemented in terms of the cover/zero arrays and the ``alternating sequence'' for Step 4 is readily constructed from the contents of ZS(), ZR() and ZP().
As an initial exploration of Munkres algorithm, consider the task of
associating two lists of random points within a 2D unit square, assuming
the cost function in Equation 9.19 is the usual
Cartesian distance. Figure 9.20 plots
total CPU times for execution of Munkres algorithm for equal size lists
versus list size. The vertical axis gives CPU times in seconds for one
node of the Mark III hypercube. The circles and crosses show the time
spent in Steps 5 and 3, respectively. These two steps (zero search
and zero manufacture) account for essentially all of the CPU
time. For the 
case, the total CPU time spent in Step 2
was about 
, and that spent in Step 4 was too small
to be reliably measured. The large amounts of time spent in Steps 3 and
5 arise from the very large numbers of times these parts of the
algorithm are executed. The 
case involves 6109 entries
into Step 3 and 593 entries into Step 5.
Since the zero searching in Step 3 of the algorithm is required so often, the implementation of this step is done with some care. The search for zeros is done column-by-column, and the code maintains pointers to both the last column searched and the most recently uncovered column (Step 3.3) in order to reduce the time spent on subsequent re-entries to the Step 3 box of Figure 9.19.
Figure 9.20: Timing Results for the Sequential Algorithm Versus Problem Size
The dashed line of Figure 9.20 indicates the nominal
scaling predicted for Munkres algorithm. By and
large, the timing results in Figure 9.20 are consistent with
this expected behavior. It should be noted, however, that both the nature of
this scaling and the coefficient of 
are very dependent on the nature
of the data sets. Consider, for example, two identical trivial lists
with the distance between items given by the absolute value function. For the
data sets in Equation 9.22, the preliminaries and Step 1 of
Munkres algorithm completely solve the association in a time which scales as
. In contrast, the random-point association problem is a much greater
challenge for the algorithm, as nominal pairings indicated by the initial
nearest-neighbor searches of the preliminary step are tediously undone in the
creation of the staircaselike sequence of zeros needed for Step 4. As a
brief, instructive illustration of the nature of this processing,
Figure 9.21 plots the CPU time per step for the last
passes through the outer loop of Figure 9.19 for the
150
150 assignment problem (recall that each pass through the outer
loop increases the 
count by one). The processing load per step is
seen to be highly nonuniform.
Figure 9.21: Times Per Loop (i.e., 
increment) for the Last Several
Loops in the Solution of the 
Problem
