On Finding a Maximal Assignment

Abstract

An algorithm is presented and justified for finding a feasible assignment of the largest possible size among the zero elements of a matrix consisting partly of zeros and partly of nonzero elements. The problem comes up at each stage of the Hungarian method for solving the assignment problem. The solution differs from other published versions following the same principle in that it is elementary yet completely specific.