Article ID: | iaor20012949 |
Country: | United States |
Volume: | 38 |
Issue: | 4 |
Start Page Number: | 985 |
End Page Number: | 1004 |
Publication Date: | Oct 1991 |
Journal: | Journal of the Association for Computing Machinery |
Authors: | Toth Paolo, Balas Egon, Miller Donald, Pekny Joseph |
Keywords: | programming: linear |
A parallel version of the shortest augmenting path algorithm for the assignment problem is described. Although generating the initial dual solution and partial assignment in parallel does not require substantive changes in the sequential algorithm, using several augmenting paths in parallel does require a new dual variable recalculation method. The parallel algorithm was tested on a 14-bit processor Butterfly Plus computer, on problems with up to 900 million variables. The speedup obtained increases with problem size. The algorithm was also embedded into a parallel branch and bound procedure for the traveling salesman problem on a directed graph, which was tested on the Butterfly Plus on problems involving up to 30,000 cities.