Article ID: | iaor1988717 |
Country: | Switzerland |
Volume: | 14 |
Start Page Number: | 105 |
End Page Number: | 123 |
Publication Date: | Sep 1988 |
Journal: | Annals of Operations Research |
Authors: | Bertsekas D.P. |
Keywords: | parallel processing |
We propose a massively parallelizable algorithm for the classical assignment problem. The algorithm operates like an auction whereby unassigned persons bid simultaneously for objects thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. The algorithm can also be interpreted as a Jacobi-like relaxation method for solving a dual problem. Its (sequential) worst-case complexity, for a particular implementation that uses scaling, is O(