{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T17:26:15Z","timestamp":1770830775324,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1995,12,1]],"date-time":"1995-12-01T00:00:00Z","timestamp":817776000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1995,12]]},"DOI":"10.1007\/bf01585996","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T08:35:26Z","timestamp":1114677326000},"page":"153-177","source":"Crossref","is-referenced-by-count":89,"title":["An efficient cost scaling algorithm for the assignment problem"],"prefix":"10.1007","volume":"71","author":[{"given":"Andrew V.","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Kennedy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1137\/S0097539791199334","volume":"23","author":"R.K. Ahuja","year":"1994","unstructured":"R.K. Ahuja, J.B. Orlin, C. Stein and R.E. Tarjan, \u201cImproved algorithms for bipartite network flow,\u201dSIAM Journal on Computing 23 (1994) 906\u2013933.","journal-title":"SIAM Journal on Computing"},{"key":"CR2","first-page":"1","volume-title":"Network Flows and Matching: First DIMACS Implementation Challenge","author":"R.J. Anderson","year":"1993","unstructured":"R.J. Anderson and J.C. Setubal, \u201cGoldberg's algorithm for the maximum flow in perspective: a computational study,\u201d 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\u201318."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02186476","volume":"14","author":"D.P. Bertsekas","year":"1988","unstructured":"D.P. Bertsekas, \u201cThe auction algorithm: a distributed relaxation method for the assignment problem,\u201dAnnals of Operations Research 14 (1988) 105\u2013123.","journal-title":"Annals of Operations Research"},{"key":"CR4","volume-title":"Linear Network Optimization: Algorithms and Codes","author":"D.P. Bertsekas","year":"1991","unstructured":"D.P. Bertsekas,Linear Network Optimization: Algorithms and Codes (MIT Press, Cambridge, MA, 1991)."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1090\/dimacs\/012\/06","volume-title":"Network Flows and Matching: First DIMACS Implementation Challenge","author":"R.G. Bland","year":"1993","unstructured":"R.G. Bland, J. Cheriyan, D.L. Jensen and L. Lada\u0144yi, \u201cAn empirical study of min cost flow algorithms,\u201d 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\u2013156."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1090\/dimacs\/012\/16","volume-title":"Network Flows and Matching: First DIMACS Implementation Challenge","author":"D.A. Casta\u00f1on","year":"1993","unstructured":"D.A. Casta\u00f1on, \u201cReverse auction algorithms for the assignment problems,\u201d 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\u2013430."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF02022037","volume":"4","author":"U. Derigs","year":"1985\u20131986","unstructured":"U. Derigs, \u201cThe shortest augmenting path method for solving assignment problems \u2014 motivation and computational experience,\u201dAnnals of Operations Research 4 (1985\u20131986) 57\u2013102.","journal-title":"Annals of Operations Research"},{"key":"CR8","first-page":"383","volume":"33","author":"U. Derigs","year":"1989","unstructured":"U. Derigs and W. Meier, \u201cImplementing Goldberg's max-flow algorithm \u2014 a computational investigation,\u201dZeitschrift f\u00fcr Operations Research 33 (1989) 383\u2013403.","journal-title":"Zeitschrift f\u00fcr Operations Research"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1090\/dimacs\/012\/09","volume-title":"Network Flows and Matching: First DIMACS Implementation Challenge","author":"S. Fujishige","year":"1993","unstructured":"S. Fujishige, K. Iwano, J. Nakano and S. Tezuka, \u201cA speculative contraction method for the minimum cost flows: toward a practical algorithm,\u201d 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\u2013246."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"H.N. Gabow","year":"1989","unstructured":"H.N. Gabow and R.E. Tarjan, \u201cFaster scaling algorithms for network problems,\u201dSIAM Journal on Computing 18 (1989) 1013\u20131036.","journal-title":"SIAM Journal on Computing"},{"key":"CR11","volume-title":"Efficient graph algorithms for sequential and parallel computers","author":"A.V. Goldberg","year":"1987","unstructured":"A.V. Goldberg, \u201cEfficient graph algorithms for sequential and parallel computers,\u201d 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)."},{"key":"CR12","first-page":"251","volume-title":"Proceedings of the Third Integer Programming and Combinatorial Optimization Conference","author":"A.V. Goldberg","year":"1993","unstructured":"A.V. Goldberg, \u201cAn efficient implementation of a scaling minimum-cost flow algorithm,\u201d in: E. Balas and J. Clausen, eds.,Proceedings of the Third Integer Programming and Combinatorial Optimization Conference (Springer, Berlin, 1993) pp. 251\u2013266."},{"key":"CR13","volume-title":"\u201cGlobal price updates help,\u201d Technical Report STAN-CS-94-1509","author":"A.V. Goldberg","year":"1994","unstructured":"A.V. Goldberg and R. Kennedy, \u201cGlobal price updates help,\u201d Technical Report STAN-CS-94-1509, Department of Computer Science, Stanford University, CA (1994)."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1090\/dimacs\/012\/07","volume-title":"Network Flows and Matching: First DIMACS Implementation Challenge","author":"A.V. Goldberg","year":"1993","unstructured":"A.V. Goldberg and M. Kharitonov, \u201cOn implementing scaling push-relabel algorithms for the minimumcost flow problem,\u201d 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\u2013198."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1006\/jagm.1993.1009","volume":"14","author":"A.V. Goldberg","year":"1993","unstructured":"A.V. Goldberg, S.A. Plotkin and P.M. Vaidya, \u201cSublinear-time parallel algorithms for matching and related problems,\u201dJournal of Algorithms 14 (1993) 180\u2013213.","journal-title":"Journal of Algorithms"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A.V. Goldberg","year":"1988","unstructured":"A.V. Goldberg and R.E. Tarjan, \u201cA new approach to the maximum flow problem,\u201dJournal of the Association for Computing Machinery 35 (1988) 921\u2013940.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1287\/moor.15.3.430","volume":"15","author":"A.V. Goldberg","year":"1990","unstructured":"A.V. Goldberg and R.E. Tarjan, \u201cFinding minimum-cost circulations by successive approximation,\u201dMathematics of Operations Research 15 (1990) 430\u2013466.","journal-title":"Mathematics of Operations Research"},{"key":"CR18","volume-title":"Network Flows and Matching: First DIMACS Implementation Challenge","year":"1993","unstructured":"D.S. Johnson and C.C. McGeoch, eds.,Network Flows and Matching: First DIMACS Implementation Challenge (American Mathematical Society, Providence, RI, 1993)."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF02278710","volume":"38","author":"R. Jonker","year":"1987","unstructured":"R. Jonker and A. Volgenant, \u201cA shortest augmenting path algorithm for dense and sparse linear assignment problems,\u201dComputing 38 (1987) 325\u2013340.","journal-title":"Computing"},{"key":"CR20","unstructured":"D. Knuth, Personal communication (1993)."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"H.W. Kuhn","year":"1955","unstructured":"H.W. Kuhn, \u201cThe Hungarian method for the assignment problem,\u201dNaval Research Logistics Quarterly 2 (1955) 83\u201397.","journal-title":"Naval Research Logistics Quarterly"},{"key":"CR22","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E.L. Lawler","year":"1976","unstructured":"E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart & Winston, New York, 1976)."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1090\/dimacs\/012\/02","volume-title":"Network Flows and Matching: First DIMACS Implementation Challenge","author":"Q.C. Nguyen","year":"1993","unstructured":"Q.C. Nguyen and V. Venkateswaran, \u201cImplementations of Goldberg\u2014Tarjan maximum flow algorithm,\u201d 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\u201342."},{"key":"CR24","series-title":"Sloan Working Paper","volume-title":"New scaling algorithms for the assignment and minimum cycle mean problems","author":"J.B. Orlin","year":"1988","unstructured":"J.B. Orlin and R.K. Ahuja, \u201cNew scaling algorithms for the assignment and minimum cycle mean problems,\u201d Sloan Working Paper 2019-88, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA (1988)."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1090\/dimacs\/012\/17","volume-title":"Network Flows and Matching: First DIMACS Implementation Challenge","author":"K.G. Ramakrishnan","year":"1993","unstructured":"K.G. Ramakrishnan, N.K. Karmarkar and A.P. Kamath, \u201cAn approximate dual projective algorithm for solving assignment problems,\u201d 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\u2013452."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585996.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01585996\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585996","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T15:32:35Z","timestamp":1556897555000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01585996"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["BF01585996"],"URL":"https:\/\/doi.org\/10.1007\/bf01585996","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}