The assignment problem (AP) seeks to minimize the cost of assigning n people to n tasks, where each assignment has a fixed cost. It can be modeled as the problem of finding a minimum cost perfect matching of a bipartite graph with bipartitions of equal order n and with fixed edge costs. A common sequential approach to AP is to use the shortest augmenting path (SAP) method, which treats AP as a special case of the minimum cost network flow problem.

This paper describes a parallel modification of SAP designed to solve AP efficiently on a non-uniform memory access architecture. The main idea of the parallelization is to have each processor construct an augmenting tree, so that multiple augmenting paths are identified in parallel. The authors show that, under conditions guaranteed by their algorithm, any set of pairwise disjoint augmenting paths created in this way is valid, and hence that their parallel procedure actually achieves the minimum cost assignment. Tests of the parallel algorithm, implemented for both sparse and dense problems on a 14-processor Butterfly computer, indicate substantial speedup over SAP and suggest that the efficiency of the algorithm depends heavily on the ratio of the range of cost values to the problem size n. The paper is well and clearly written with adequate references; it is addressed to an audience already familiar with AP algorithms.