Portal de Periódicos da CAPES

A new algorithm for the assignment problem

1981; Springer Science+Business Media; Volume: 21; Issue: 1 Linguagem: Inglês

10.1007/bf01584237

1436-4646

Dimitri P. Bertsekas,

Optimization and Packing Problems

We propose a new algorithm for the classical assignment problem. The algorithm resembles in some ways the Hungarian method but differs substantially in other respects. The average computational complexity of an efficient implementation of the algorithm seems to be considerably better than the one of the Hungarian method. In a large number of randomly generated problems the algorithm has consistently outperformed an efficiently coded version of the Hungarian method by a broad margin. The factor of improvement increases with the problem dimensionN and reaches an order of magnitude forN equal to several hundreds.