The auction algorithm: A distributed relaxation method for the assignment problem

The auction algorithm: A distributed relaxation method for the assignment problem

0.00 Avg rating0 Votes
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:
Keywords: parallel processing
Abstract:

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(MAlog(NC)), where N is the number of persons, A is the number of pairs of persons and objects that can be assigned to each other, and C is the maximum absolute object value. Computational results show that, for large problems, the algorithm is competitive with existing methods even without the benefit of parallelism. When executed on a parallel machine, the algorithm exhibits substantial speedup.

Reviews

Required fields are marked *. Your email address will not be published.