{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,21]],"date-time":"2026-11-21T17:43:33Z","timestamp":1795283013823,"version":"4.10.3"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1989,10]]},"abstract":"<jats:p>This paper presents algorithms for the assignment problem, the transportation problem, and the minimum-cost flow problem of operations research. The algorithms find a minimum-cost solution, yet run in time close to the best-known bounds for the corresponding problems without costs. For example, the assignment problem (equivalently, minimum-cost matching in a bipartite graph) can be solved in $O(\\sqrt {nm} \\log (nN))$ time, where $n,m$, and N denote the number of vertices, number of edges, and largest magnitude of a cost; costs are assumed to be integral. The algorithms work by scaling. As in the work of Goldberg and Tarjan, in each scaled problem an approximate optimum solution is found, rather than an exact optimum.<\/jats:p>","DOI":"10.1137\/0218069","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:32:44Z","timestamp":1109226764000},"page":"1013-1036","source":"Crossref","is-referenced-by-count":268,"title":["Faster Scaling Algorithms for Network Problems"],"prefix":"10.1137","volume":"18","author":[{"given":"Harold N.","family":"Gabow","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RAGOT","doi-asserted-by":"crossref","unstructured":"R. K. Ahuja, A. V. Goldberg, J. B. Orlin, R. E. Tarjan,  Finding minimum-cost flows by double scaling,  1988, Tech. Report CS-TR-164-88, Dept. of Comput. Sci., Princeton University, Princeton, NJ, submitted for publication","DOI":"10.21236\/ADA214498"},{"key":"RAHU","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"RAL","unstructured":"A. V. Aho, D. Lee,  Efficient algorithms for constructing testing sets, covering paths, and minimum flows,  1988, unpublished manuscript"},{"key":"RBA","unstructured":"C. A. Bateson, Masters Thesis,  Performance comparison of two algorithms for weighted bipartite matching, M.S. thesis, Dept. of Comput. Sci., University of Colorado, Boulder, CO,  1985"},{"key":"RBEL","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"RBER79","unstructured":"D. P. Bertsekas,  A distributed algorithm for the assignment problem,  1979, unpublished working paper, Laboratory for Information and Decision Sciences, Mass. Inst. of Technology, Cambridge, MA"},{"key":"RBER86","doi-asserted-by":"crossref","unstructured":"D. P. Bertsekas,  Distributed asynchronous relaxation methods for linear network flow problems, LIDS Report, P-1606, Mass. Inst. of Technology, Cambridge, MA,  1986, preliminary version in Proc. 25th IEEE Conference on Decision and Control, December 1986","DOI":"10.1109\/CDC.1986.267433"},{"key":"RBER87","unstructured":"D. P. Bertsekas,  The auction algorithm: A distributed relaxation method for the assignment problem, LIDS Report, P-1653, Mass. Inst. of Technology, Cambridge, MA,  1987"},{"key":"RD","doi-asserted-by":"publisher","DOI":"10.1145\/363269.363610"},{"key":"REJ","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580113"},{"key":"REK","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"RET","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"RFT","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"RG85","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90039-X"},{"key":"RG87","unstructured":"H. N. Gabow,  Duality and parallel algorithms for graph matching,  1987, unpublished manuscript"},{"key":"RGABT88","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, R. E. Tarjan,  Almost-optimum speed-ups of algorithms for bipartite matching and related problems,  1988, Proc. 20th Annual ACM Symposium on Theory of Computing, pp. 514\u2013527; submitted for publication","DOI":"10.1145\/62212.62263"},{"key":"RGABT89","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, R. E. Tarjan,  Faster scaling algorithms for general graph matching problems,  1989, Tech. Report CU-CS-432-89, Dept. of Comput. Sci., University of Colorado, Boulder, CO; submitted for publication","DOI":"10.21236\/ADA215112"},{"key":"RGX89A","unstructured":"H. N. Gabow, Y. Xu,  Efficient theoretic and practical algorithms for linear matroid intersection problems,  1989, Tech. Report CU-CS-424-89, Dept. of Comput. Sci., University of Colorado, Boulder, CO; submitted for publication"},{"key":"RGX89B","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, Y. Xu,  Efficient algorithms for independent assignment on graphic and linear matroids,  1989, Proc. 30th Annual Symposium on Foundations of Computer Science, to appear","DOI":"10.1109\/SFCS.1989.63463"},{"key":"RGALT","doi-asserted-by":"crossref","unstructured":"Z. Galil, \u00c9. Tardos,  An  O(n2(m+nlogn)logn) min-cost flow algorithm,  Proc. 27th Annual Symposium on Foundations of Computer Science,  1986,  1\u20139","DOI":"10.1109\/SFCS.1986.7"},{"key":"RGJ","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"RGO","unstructured":"A. V. Goldberg,  Efficient graph algorithms for sequential and parallel computers, Tech. Report, MIT\/LCS\/TR-374, Dept. of Electrical Engrg. and Comput. Sci., Mass. Inst. of Technology, Cambridge, MA,  1987, Ph.D. dissertation"},{"key":"RGOT86","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"RGOT87A","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg, R. E. Tarjan,  Solving minimum-cost flow problems by successive approximation,  Proc. 19th Annual ACM Symposium on Theory of Computing,  1987,  7\u201318","DOI":"10.1145\/28395.28397"},{"key":"RGOT87B","doi-asserted-by":"publisher","DOI":"10.1287\/moor.15.3.430"},{"key":"RH","unstructured":"P. P. Herrmann,  On reducibility among combinatorial problems, Report, TR-113, Project MAC, Mass. Inst. of Technology, Cambridge, MA,  1973"},{"key":"RHK","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"RK55","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"RK56","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030404"},{"key":"RL","volume-title":"Combinatorial optimization: networks and matroids","author":"Lawler E. L.","year":"1976"},{"key":"ROA","unstructured":"J. B. Orlin, R. K. Ahuja,  New scaling algorithms for the assignment and minimum cycle mean problems, Sloan Working Paper, 2019-88, Sloan School of Management, Mass. Inst. of Technology, Cambridge, MA,  1988"},{"key":"RPS","volume-title":"Combinatorial optimization: algorithms and complexity","author":"Papadimitriou Christos H.","year":"1982"},{"key":"RTARD","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579369"},{"key":"RTARJ","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"},{"key":"RW","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321927"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0218069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:45:13Z","timestamp":1787337913000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0218069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,10]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1989,10]]}},"alternative-id":["10.1137\/0218069"],"URL":"https:\/\/doi.org\/10.1137\/0218069","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,10]]}}}