|Create Date||September 26, 2014|
|Last Updated||April 16, 2015|
The linear sum assignment problem (LSAP) is a classical combinatorial optimization problem that is found in many applications. The assignment problem deals with the question of how to assign n persons to n objects in the best possible way.
In this paper we explore the worst case performance aspects of the algorithm. We prove that the algorithm is finite and analyse its computational complexity.
It also discusses a number of simplified variations of the algorithm that shed some light on how the algorithm works.
Computational results on a number of problem types show that the solutions reached by our algorithm are only slightly worse than those obtained by the auction algorithm.
|Speed and optimality of the Deep Greedy switching algorithm for linear assignment problems|