A Primal Method for the Assignment and Transportation Problems

Abstract

This paper describes a simple calculation for the assignment and transportation problems which is “dual to” the well-known Hungarian Method. While the Hungarian is a dual method, this method is primal and so gives a feasible assignment at each stage of the calculation. Bounds on the number of steps required for the assignment and transportation problems are given. They are the same as the best bounds known for the Hungarian Method.