L. Buš and P. Tvrdík (Czech Republic)
Distributed Algorithm, Linear Sum Assignment Problem, Auction Algorithm, Linear Optimization
The Linear Sum Assignment Problem (LSAP) consists in finding a minimum cost assignment of Ò objects to Ò per sons given a cost Ò ¢Ò matrix. We have developed a suite of distributed memory parallel auction algorithms (AA) for solving the LSAP and implemented them in MPI-1 on a PC cluster with a Myrinet network. The suite includes for ward, reverse, and forward-reverse AAs, all with or without scaling the bidding increment. The subset of free persons acting in parallel in the auction can be chosen adaptively during the computation and this feature, called block-size adaptivity, allows to tune the parallel AAs for optimum per formance. Our algorithms allow to solve large-scale LSAP instances by allocating enough processors with sufficient total capacity of RAM memory, so that the effect of mem ory swapping is eliminated.
Important Links:
Go Back
