Algorithms and codes for dense assignment problems: the state of the art

The paper considers the classic linear assignment problem with a min-sum ob jective function, and the most efficient and easily available codes for its solution, We first give a survey describing the different approaches in th e literature, presenting their implementations, and pointing out similariti es and differences, Then we select eight codes and we introduce a wide set of dense instances containing both randomly generated and benchmark problem s. Finally we discuss the results of extensive computational experiments ob tained by solving the above instances with the eight codes, both on a works tation with Unix operating system and on a personal computer running under Windows 95. (C) 2000 Elsevier Science B.V. All rights reserved.