A Primal Method for the Assignment and Transportation Problems

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.

• 저널Management Science · 10(3) · 578–593
• 토픽Optimization and Mathematical Programming · Control and Systems Engineering
• DOI10.1287/mnsc.10.3.578
• 저자Michel Balinski, Ralph E. Gomory