An Empirical Analysis of the Dense Assignment Problem: Sequential and Parallel Implementations

• Published in: INFORMS journal on computing 1991-11, Vol.3 (4), p.299-306
• Main Authors: Kennington, Jeffery L, Wang, Zhiming
• Format: Article
• Language: English
• Subjects: matchings: algorithms for dense assignment problems; networks
• ISSN: 0899-1499; 1526-5528; 2326-3245
• DOI: 10.1287/ijoc.3.4.299

The best algorithms for the dense assignment problem are acknowledged to be the auction algorithm and the shortest augmenting path algorithm. In this investigation we present an empirical analysis of two of the current best software implementations of these two methods on three different serial machines. These software implementations were developed by D. P. Bertsekas of the Massachusetts Institute of Technology and by R. Jonker and T. Volgenant of the University of Amsterdam. This report is an independent evaluation of the software implementation of these two algorithms. For the sample of problems examined and the sample of hardware used (IBM 3081D, Sequent Symmetry S81, and VAX 750), we found that the shortest augmenting path algorithm was the fastest. We also report our empirical results with a parallel version of the shortest augmenting path algorithm. On 1200 x 1200 dense assignment problems, speedups of approximately four were achieved using ten processors. Million arc problems were solved in less than twelve seconds on a Sequent Symmetry S81 with the parallel shortest augmenting path algorithm. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.