Abstract
Balinski uses his signature method for the proof of the Hirsch-conjecture for dual transportation polyhedra to obtain an efficient algorithm for the assignment problem. We will show how to extend this method to other primal transportation problems, including transportation problems with unit demands. We then prove that Balinski's assignment algorithm is equivalent, cycle by cycle, to that of Hung and Rom. We demonstrate that, under some assumptions for our probability model, a modification of the latter algorithm has an average complexity of O(n 2logn) and present some computational results confirming this. We also present results that indicate that this modification compares favorably with Balinski's algorithm and other codes.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M.L. Balinski, “On two special classes of transportation polytopes,”Mathematical Programming Study 1 (1974) 43–58.
M.L. Balinski, “The Hirsch conjecture for dual transportation polyhedra,”Mathematics of Operations Research 9 (1984) 629–633.
M.L. Balinski, “Signature methods for the assignment problem,”Operations Research 33 (1985) 527–536.
M.L. Balinski “A competitive (dual) simplex method for the assignment problem,”Mathematical Programming 34 (1986) 125–141.
R.E. Burkard and U. Derigs,Assignment and Matching Problems: Solution Methods with FORTRAN-Programs (Springer, Berlin, Heidelberg, New York, 1980).
G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, New Jersey, 1963).
G.B. Dantzig, “Eight unsolved problems from mathematical programming,”Bulletin of the American Mathematical Society 70 (1964) 499–500.
L.R. Ford and D.R. Fulkerson,Flows, in Networks (Princeton University Press, Princeton, New Jersey, 1962).
D. Goldfarb, “Eflicient dual simplex algorithms for the assignment problem,”Mathematical Programming 33 (1985) 969–982.
M.S. Hung and W.D. Rom, “Solving the assignment problem by relaxation,”Operations Research 28 (1980) 969–982.
V.L. Klee and P. Kleinschmidt, “The d-step conjecture and its relatives,”Mathematics of Operations Research to appear.
V.L. Klee and D.W. Walkup, “The d-step conjecture for polyhedra of dimensiond<6,”Acta Mathematica 133 (1967) 53–78.
J. Riordan,An Introduction to Combinatorial Analysis (Wiley, New York, 1958).
R. Silver, “An algorithm for the assignment problem,”Communications of the Association of Computing Machinery 3 (1960) 603–606.
N. Tomizawa, “On some techniques useful for solution of transportation network problems,”Networks 1 (1972) 179–194.
Author information
Authors and Affiliations
Additional information
Research of both authors supported, in part, by grants of the Alexander von Humboldt-Stiftung.
Supported, in part, by NSF grant DMS-8504050.
Rights and permissions
About this article
Cite this article
Kleinschmidt, P., Lee, C.W. & Schannath, H. Transportation problems which can be solved by the use of hirsch-paths for the dual problems. Mathematical Programming 37, 153–168 (1987). https://doi.org/10.1007/BF02591692
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02591692