An Approximate Dual Projective Algorithm for Solving Assignment Problems

This paper discusses a new algorithm for solving the assignment problem. This algorithm, called the Approximate Dual Projective algorithm for assignment (ADP/A), is a variant of the Karmarkar interior point algorithm for LPs, specialized to solve the assignment problem. Computational results are reported on various classes of assignment problems. These results indicate that this method, holds promise for solving large assignment problems