A relaxation column signature method for assignment problems

A recent computational study on algorithms for assignment problems revealed that the so called Modified Hung-Rom Algorithm (MHRA) performs very well in practice. The MHRA is a row signature method and its effectiveness comes mainly from its capability to reduce the level by more than one unit per cycle. The paper presents an O(n³) column signature method which has the above mentioned capability. The algorithm solves a sequence of relaxed transportation problems and generates strong dual feasible bases. It is shown that the average number of iterations is bounded by nlogn. A result on Balinski’s strong dual feasible bases is also presented.