A new algorithm for the assignment problem: An alternative to the Hungarian method

This paper presents a new algorithm for the well-studied assignment problem. Our assignment algorithm is based on a 2n × 2n matrix. The dual to the assignment problem is considered in this paper by relaxing the constraints of the original assignment problem. A 2n × 2n matrix is formed for an initial feasible solution to the dual. Then operations are performed on the matrix until an optimal solution is found.