A relaxation column signature method for assignment problems (Q1814258)

The author presents a column signature method for solving assignment problems. It is shown that by this method an \(n\times n\) assignment problem can be solved in at most \({1 \over 2}(n-1)(n-2)\) iterations and in at most \(O(n^ 3)\) elementary operations. It is also shown that the average number of iterations required by the method to arrive at a solution is bounded from above by \(n \log n\). Some similarities between the presented method and other known methods including the modified Hung- Rom algorithm [\textit{M. S. Hung} and \textit{W. O. Rom}, Oper. Res. 28, 969- 982 (1980; Zbl 0441.90062)] are discussed at the end.