ISSN:
1436-4646
Keywords:
Assignment Problems
;
Network Flows
;
Hungarian Method
;
Computational Complexity
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01584237
Permalink
