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

- M1:
- Modifications of the distance matrix
**D**by row/column subtractions, creating a (large) number of zero entries. - M2:
- With 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**

- Step 1:
- Setup
- Find a zero
**Z**in the distance matrix. - If there is no starred zero already in its row or column, star this zero.
- Repeat steps 1.1, 1.2 until all zeros have been considered.

- Find a zero
- Step 2:
- Count, Solution Assessment
- Cover every column containing a .
- Terminate the algorithm if all columns are covered. In this case, the locations of the entries in the matrix provide the solution to the assignment problem.

- Step 3:
- Main Zero Search
- Find an uncovered
**Z**in the distance matrix and prime it, . If no such zero exists, go to Step 5 - If No exists in the row of the , go to Step 4.
- If a exists, cover this row and uncover the column of
the . Return to Step 3.1 to find a new
**Z**.

- Find an uncovered
- Step 4:
- Increment Set of Starred Zeros
- Construct the ``alternating sequence'' of primed and starred zeros:
- : 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

**N**. - Unstar each starred zero of the sequence.
- Star each primed zero of the sequence, thus increasing the number of starred zeros by one.
- Erase all primes, uncover all columns and rows, and return to Step 2.

- Construct the ``alternating sequence'' of primed and starred zeros:
- Step 5:
- New Zero Manufactures
- Let
**h**be the smallest uncovered entry in the (modified) distance matrix. - Add
**h**to all covered rows. - Subtract
**h**from all uncovered columns - Return to Step 3, without altering stars, primes, or covers.

- Let

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:

- CC:
- Covered column tags, .
- CR:
- Covered row tags,
- ZS:
- locators for columns of the matrix. If positive, ZS is the row index of the in the column of the matrix.
- ZR:
- locators for rows of the matrix. If positive, ZR is the column of the in the row of the matrix.
- ZP:
- 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
150150 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

Wed Mar 1 10:19:35 EST 1995