Ingeniero

A Primal Method for the Assignment and Transportation Problems Author(s): M. L. Balinski and R. E. Gomory Source: Management Science, Vol. 10, No. 3 (Apr., 1964), pp. 578-593 Published by: INFORMS Stable URL: http://www.jstor.org/stable/2627433 . Accessed: 02/03/2011 16:04
Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at .http://www.jstor.org/page/info/about/policies/terms.jsp. JSTOR's Terms and Conditions of Use provides, in part, that unless you have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you may use content in the JSTOR archive only for your personal, non-commercial use. Please contact the publisher regarding any further use of this work. Publishercontact information may be obtained at . http://www.jstor.org/action/showPublisher?publisherCode=informs. . Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed page of such transmission. JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in atrusted digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about JSTOR, please contact support@jstor.org.

INFORMS is collaborating with JSTOR to digitize, preserve and extend access to Management Science.

http://www.jstor.org

MANAGEMENT SCIENCE Vol. 10, No. 3, April, 1964 Printed in U.S.A.

A PRIMALMETHOD FOR THE ASSIGNMENT AND TRANSPORTATION PROBLEMS*t
M. L. BALINSKI'
AND

R. E. GOMORY2

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 stepsrequired for the assignment and transportation problems are given. They are the same as the best bounds known for the Hungarian Method.

1. Introduction Perhaps the best known, most widely used, and most written about method for solving the assignment problem is the "Hungarian Method". Originally suggested by Kuhn [8] in 1955, it has appeared in many variants (e.g., [4], [5], [9], [10], [11]). Itprovided essential ideas for the early methods used in solving network flow problems [5], it has been extended to solve the transportation problem [51, [11], and it has even been "generalized" to solve the linear programming problem [3]. It is a dual method with a feasible assignment being obtained only at the last computational step. This paper presents a primal method for the assignment andtransportation problems which is a method "dual to" the Hungarian Method. Where the Hungarian Method provides at each intermediate computational step a dual feasible vector (U, V) and a corresponding (infeasible) primal vector X orthogonal to (U, V), the present method provides at each step a feasible X (a complete assignment or transportation solution) and a corresponding orthogonal (U, V). Inaddition to the advantage of being primal, and so providing a constantly improving solution, the method seems to be extremely simple to describe, explain, and-it would seem-program. With this method, we are able to bound the number of steps required to solve the assignment and transportation problems. Different bounds can be obtained from different variants of the procedure. The best bounds are n(n +1)/2 labeling passes for the n X n assignment problem and (Zjcj) min (m, n) passes for the m source n sink transportation problem with total demand of Ej Cj . These bounds are the same as the best known bounds for the Hungarian Method. Remarkably enough, the variant that gives the best bounds requires a special rule of choice very similar to the simplex method's "most negative column" rule.
*...