L. Buš and P. Tvrdík (Czech Republic)
Parallel Algorithms and Architectures, Linear Sum Assign ment Problem, Auction Algorithm, Linear Optimization, Distributed Algorithms
In this paper, we present a new auction algorithm for the linear assignment problem, based on a new technique, called look-back bidding. The main idea is to keep local working sets of objects. It leads to significant performance gains both in sequential and distributed memory parallel versions. We give performance results of the new algo rithm, called look-back auction algorithm, and compare its complexity with standard auction algorithms. In the par allel version, our new algorithm eliminates a substantial amount of interprocessor communication.
Important Links:
Go Back
