A centrally coordinated parallel auction algorithm for large scale assignment problems

We present a novel parallel auction algorithm implementation for solving the linear sum assignment problem. It is implemented using the message passing interface (MPI) on a computer cluster. Our approach enables dynamic computational load balancing over all processors throughout all steps of the algorithm´s execution. We show that the performance of our approach is superior to existing approaches in the literature.