A new algorithm for the assignment problem. (English) Zbl 0461.90069


90C35 Programming involving graphs or networks
68Q25 Analysis of algorithms and problem complexity
65K05 Numerical mathematical programming methods
90B10 Deterministic network models in operations research
90C05 Linear programming
Full Text: DOI


[1] E. Lawler,Combinatorial optimization: networks and matroids (Holt, Rinehart and Winston, 1976). · Zbl 0413.90040
[2] H.W. Kuhn, ”The Hungarian method for the assignment problem”,Naval Research Logistics Quarterly 2 (1955) 83–97. · Zbl 0143.41905 · doi:10.1002/nav.3800020109
[3] R.S. Barr, F. Glover and D. Klingman, ”The alternating basis algorithm for assignment problems”,Mathematical Programming 13 (1977) 1. · Zbl 0378.90097 · doi:10.1007/BF01584319
[4] G.H. Bradley, G.G. Brown and G.W. Graves, ’Design and implementation of large scale primal transhipment algorithms”,Management Science 24 (1977) 1. · Zbl 0373.90079 · doi:10.1287/mnsc.24.1.1
[5] R.V. Helgason and J.L. Kennigton, ”NETFLOW program documentation”, technical report IEOR 76011, Department of Industrial Engineering and Operations Research, Southern Methodist University (1976).
[6] R.S. Hatch, ”Bench marks comparing transportation codes based on primal simplex and primal–dual algorithms”,Operations Research 23 (1975) 1167. · Zbl 0313.90041 · doi:10.1287/opre.23.6.1167
[7] L.F. McGinnis, ”Implementation and testing of a primal–dual algorithm for the assignment problem”, Industrial and Systems Engineering report series No. J-78-31, Georgia Institute of Technology (November 1978).
[8] A. Weintraub, and F. Barahona, ”A dual algorithm for the assignment problem”, Departmento de Industrias Report No. 2, Universidad de Chile-Sede Occidente (April 1979).
[9] F. Glover and D. Klingman, ”Comment on a note by Hatch on network algorithms”Operations Research 26 (1978) 370. · doi:10.1287/opre.26.2.370
[10] J. Edmonds and R. Karp, ”Theoretical improvements in algorithmic efficiency for network flow problems”,Journal of the Association for Computing Machinery 19 (1972) 248–264. · Zbl 0318.90024
[11] D.P. Bertsekas, ”An algorithm for the Hitchcock transportation problem”,Proceedings of the 18 th Allerton conference on communication, control and computing, Allerton Park, 11 Oct. 1979.
[12] M.D. Grigoriadis, Talk at Mathematical Programming Symposium, Montreal, August 1979 (also private communication).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.