Solving the Assignment Problem by Relaxation

Abstract

This paper presents a new algorithm for solving the assignment problem. The algorithm is based on a scheme of relaxing the given problem into a series of simple network flow (transportation) problems for each of which an optimal solution can be easily obtained. The algorithm is thus seen to be able to take advantage of the nice properties in both the primal and the dual approaches for the assignment problem. The computational bound for the algorithm is shown to be 0(n 3 ) and the average computation time is better than most of the specialized assignment algorithms.