| Article ID: | iaor19981331 |
| Country: | United States |
| Volume: | 38 |
| Issue: | 4 |
| Start Page Number: | 985 |
| End Page Number: | 1004 |
| Publication Date: | Apr 1991 |
| Journal: | Journal of the Association for Computing Machinery |
| Authors: | Toth Paolo, Miller David M., Balas E., Pekny J. |
| Keywords: | computational analysis: parallel computers, programming: travelling salesman, programming: assignment |
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 speed-up obtained increases with problem size. The algorithm was also embedded into a parallel branch and bound procedure for the travelling salesman problem on a directed graph, which was tested on the Butterfly Plus on problems involving up to 30,000 cities.