Abstract
The cost scaling push-relabel method has been shown to be efficient for solving minimum-cost flow problems. In this paper we apply the method to the assignment problem and investigate implementations of the method that take advantage of assignment's special structure. The results show that the method is very promising for practical use.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R.K. Ahuja, J.B. Orlin, C. Stein and R.E. Tarjan, “Improved algorithms for bipartite network flow,”SIAM Journal on Computing 23 (1994) 906–933.
R.J. Anderson and J.C. Setubal, “Goldberg's algorithm for the maximum flow in perspective: a computational study,” in: D.S. Johnson and C.C. McGeoch, eds.,Network Flows and Matching: First DIMACS Implementation Challenge (American Mathematical Society, Providence, RI, 1993) pp. 1–18.
D.P. Bertsekas, “The auction algorithm: a distributed relaxation method for the assignment problem,”Annals of Operations Research 14 (1988) 105–123.
D.P. Bertsekas,Linear Network Optimization: Algorithms and Codes (MIT Press, Cambridge, MA, 1991).
R.G. Bland, J. Cheriyan, D.L. Jensen and L. Ladańyi, “An empirical study of min cost flow algorithms,” in: D.S. Johnson and C.C. McGeoch, eds.,Network Flows and Matching: First DIMACS Implementation Challenge (American Mathematical Society, Providence, RI, 1993) pp. 119–156.
D.A. Castañon, “Reverse auction algorithms for the assignment problems,” in: D.S. Johnson and C.C. McGeoch, eds.,Network Flows and Matching: First DIMACS Implementation Challenge (American Mathematical Society, Providence, RI, 1993) pp. 407–430.
U. Derigs, “The shortest augmenting path method for solving assignment problems — motivation and computational experience,”Annals of Operations Research 4 (1985–1986) 57–102.
U. Derigs and W. Meier, “Implementing Goldberg's max-flow algorithm — a computational investigation,”Zeitschrift für Operations Research 33 (1989) 383–403.
S. Fujishige, K. Iwano, J. Nakano and S. Tezuka, “A speculative contraction method for the minimum cost flows: toward a practical algorithm,” in: D.S. Johnson and C.C. McGeoch, eds.,Network Flows and Matching: First DIMACS Implementation Challenge (American Mathematical Society, Providence, RI, 1993) pp. 219–246.
H.N. Gabow and R.E. Tarjan, “Faster scaling algorithms for network problems,”SIAM Journal on Computing 18 (1989) 1013–1036.
A.V. Goldberg, “Efficient graph algorithms for sequential and parallel computers,” Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA (1987); also: Technical Report TR-374, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA (1987).
A.V. Goldberg, “An efficient implementation of a scaling minimum-cost flow algorithm,” in: E. Balas and J. Clausen, eds.,Proceedings of the Third Integer Programming and Combinatorial Optimization Conference (Springer, Berlin, 1993) pp. 251–266.
A.V. Goldberg and R. Kennedy, “Global price updates help,” Technical Report STAN-CS-94-1509, Department of Computer Science, Stanford University, CA (1994).
A.V. Goldberg and M. Kharitonov, “On implementing scaling push-relabel algorithms for the minimumcost flow problem,” in: D.S. Johnson and C.C. McGeoch, eds.,Network Flows and Matching: First DIMACS Implementation Challenge (American Mathematical Society, Providence, RI, 1993) pp. 157–198.
A.V. Goldberg, S.A. Plotkin and P.M. Vaidya, “Sublinear-time parallel algorithms for matching and related problems,”Journal of Algorithms 14 (1993) 180–213.
A.V. Goldberg and R.E. Tarjan, “A new approach to the maximum flow problem,”Journal of the Association for Computing Machinery 35 (1988) 921–940.
A.V. Goldberg and R.E. Tarjan, “Finding minimum-cost circulations by successive approximation,”Mathematics of Operations Research 15 (1990) 430–466.
D.S. Johnson and C.C. McGeoch, eds.,Network Flows and Matching: First DIMACS Implementation Challenge (American Mathematical Society, Providence, RI, 1993).
R. Jonker and A. Volgenant, “A shortest augmenting path algorithm for dense and sparse linear assignment problems,”Computing 38 (1987) 325–340.
D. Knuth, Personal communication (1993).
H.W. Kuhn, “The Hungarian method for the assignment problem,”Naval Research Logistics Quarterly 2 (1955) 83–97.
E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart & Winston, New York, 1976).
Q.C. Nguyen and V. Venkateswaran, “Implementations of Goldberg—Tarjan maximum flow algorithm,” in: D.S. Johnson and C.C. McGeoch, eds.,Network Flows and Matching: First DIMACS Implementation Challenge (American Mathematical Society, Providence, RI, 1993) pp. 19–42.
J.B. Orlin and R.K. Ahuja, “New scaling algorithms for the assignment and minimum cycle mean problems,” Sloan Working Paper 2019-88, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA (1988).
K.G. Ramakrishnan, N.K. Karmarkar and A.P. Kamath, “An approximate dual projective algorithm for solving assignment problems,” in: D.S. Johnson and C.C. McGeoch, eds.,Network Flows and Matching: First DIMACS Implementation Challenge (American Mathematical Society, Providence, RI, 1993) pp. 431–452.
Author information
Authors and Affiliations
Additional information
This author's research was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC and 3M, and a grant from the Powell Foundation.
This author's research was supported by the above-mentioned ONR and NSF grants.
Rights and permissions
About this article
Cite this article
Goldberg, A.V., Kennedy, R. An efficient cost scaling algorithm for the assignment problem. Mathematical Programming 71, 153–177 (1995). https://doi.org/10.1007/BF01585996
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585996