An infeasible (exterior point) simplex algorithm for assignment problems

The so called Modified Hung-Rom Algorithm, based upon theoretical considerations of Hirsch-paths, seems to be one of the most efficient algorithms for assignment problems. Since any two basic feasible solutions to a linear problem can always be connected with a short simplex path passing through the infeasible region, development of algorithms based upon theoretical considerations on infeasible paths seems to be of great practical interest. This paper presents an algorithm of this kind for assignment problems.