The authors present the results of implementing algorithms for the augmenting path problem with dense linear assignments. Two initialization algorithms are parallelized: a naive approach and an initialization based on work by Jonker and Volgenant. Two augmentation algorithms are parallelized: an algorithm based on work by Jonker and Volgenant and an algorithm based on work by Carpaneto, Martello, and Toth.

Computational experiments are reported for the MasPar MP-2. Experimental results are presented for the four combinations of initialization and augmentation algorithms with varying cost ranges and varying problem sizes. With problem size n and cost range R the authors summarize their results as follows: For n &slash; R < 3 the naive initialization is preferable; for n &slash; R ≥ 3 the Jonker and Volgenant initialization is asymptotically better; and for n &slash; R < 2 the Jonker and Volgenant augmentation algorithm is better, while the Carpaneto, Martello, and Toth augmentation algorithm is more efficient otherwise.