{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T16:59:31Z","timestamp":1638291571608},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1989,10]]},"abstract":"\n A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and\n canceling<\/jats:italic>\n it by pushing enough flow around the cycle to saturate an arc. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. This gives a very simple strongly polynomial algorithm that uses no scaling. A variant of the algorithm that uses dynamic trees runs in \u039f(\n nm<\/jats:italic>\n (log\n n<\/jats:italic>\n )min{log(\n nC<\/jats:italic>\n ),\n m<\/jats:italic>\n log\n n<\/jats:italic>\n }) time on a network of\n n<\/jats:italic>\n vertices,\n m<\/jats:italic>\n arcs, and arc costs of maximum absolute value\n C<\/jats:italic>\n . This bound is comparable to those of the fastest previously known algorithms.\n <\/jats:p>","DOI":"10.1145\/76359.76368","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"873-886","source":"Crossref","is-referenced-by-count":177,"title":["Finding minimum-cost circulations by canceling negative cycles"],"prefix":"10.1145","volume":"36","author":[{"given":"Andrew V.","family":"Goldberg","sequence":"first","affiliation":[{"name":"Stanford Univ., Stanford, CA"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[{"name":"Princeton Univ., Princeton, NJ"}]}],"member":"320","reference":[{"key":"e_1_2_1_3_2","unstructured":"AHUJA R. K. ORLIN J. B. AND TARJAN R.E. Improved time bounds for the maximum flow problem. SlAM J. Comput. to appear. 10.1137\/0218065 AHUJA R. K. ORLIN J. B. AND TARJAN R.E. Improved time bounds for the maximum flow problem. SlAM J. Comput. to appear. 10.1137\/0218065"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218039"},{"key":"e_1_2_1_7_2","volume-title":"McGraw-Hill","author":"BUSACKER R. G.","year":"1965"},{"key":"e_1_2_1_8_2","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in networks with power estimation","volume":"11","author":"DINIC E.A","journal-title":"Soviet Math. Dokl."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"FORD JR. L. R. AND FULKERSON D.R. Flows in Networks. Princeton Univ. Press Princeton N.J. 1962. FORD JR. L. R. AND FULKERSON D.R. Flows in Networks. Princeton Univ. Press Princeton N.J. 1962.","DOI":"10.1515\/9781400875184"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580882"},{"key":"e_1_2_1_13_2","unstructured":"GABOW H. N. AND TARJAN R. E. Faster scaling algorithms for network problems. SlAM J. Comput. to appear. 10.1137\/0218069 GABOW H. N. AND TARJAN R. E. Faster scaling algorithms for network problems. SlAM J. Comput. to appear. 10.1137\/0218069"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/42282.214090"},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"GOLDBERG A. V. AND TARJAN R. E. Finding minimum-cost circulations by successive approximation. Math. Oper. Res. to appear. 10.1287\/moor.15.3.430 GOLDBERG A. V. AND TARJAN R. E. Finding minimum-cost circulations by successive approximation. Math. Oper. Res. to appear. 10.1287\/moor.15.3.430","DOI":"10.1287\/moor.15.3.430"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_2_1_18_2","first-page":"7","volume-title":"Proceedings of the 19th ACM Symposium on Theory of Computing","author":"GOLDBERG A. V.","year":"1987"},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","article-title":"A characterization of the minimum cycle mean in a digraph","volume":"23","author":"KARP R. M","year":"1978","journal-title":"Discrete Math."},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0166-218X(81)90026-3","article-title":"Parametric shortest path algorithms with an application to cyclic staffing","volume":"3","author":"KARP R. M.","year":"1981","journal-title":"Discrete Appl. Math."},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1287\/mnsc.14.3.205","article-title":"A primal method for minimal cost flows with applications to the assignment and transportation problems","volume":"14","author":"KLEIN M","year":"1967","journal-title":"Manage. Sci."},{"key":"e_1_2_1_22_2","unstructured":"LAWLER E~ L. Combinatorial Optimization: Networks and Matroids. Holt Reinhart and Winston New York N.Y. 1976. LAWLER E~ L. Combinatorial Optimization: Networks and Matroids. Holt Reinhart and Winston New York N.Y. 1976."},{"key":"e_1_2_1_24_2","first-page":"166","article-title":"On the simplex algorithm for networks and generalized networks. Math. Prog","volume":"24","author":"ORLIN J.B","year":"1985","journal-title":"Studies"},{"key":"e_1_2_1_25_2","first-page":"377","volume-title":"Proceedings of the 20th ACM Symposium on Theory of Computing","author":"ORLIN J.B."},{"key":"e_1_2_1_26_2","volume-title":"Mass.","author":"ORLIN J. B.","year":"1988"},{"key":"e_1_2_1_27_2","unstructured":"PAPADIMITRIOU C. H. AND STEIGLITZ K. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall Englewood Cliffs N.J. 1982. PAPADIMITRIOU C. H. AND STEIGLITZ K. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall Englewood Cliffs N.J. 1982."},{"key":"e_1_2_1_28_2","first-page":"181","article-title":"Scaling techniques for minimal cost network flows. In Discrete Structures and Algorithms, U. Pape, Ed. Carl Hansen, Miinich","author":"ROCK H","year":"1980","journal-title":"W. Germany"},{"key":"e_1_2_1_29_2","volume-title":"Calif.","author":"SLEATOR D.D.","year":"1980"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579369"},{"key":"e_1_2_1_33_2","volume-title":"Pa.","author":"TARJAN R. E.","year":"1983"},{"key":"e_1_2_1_34_2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","article-title":"Design and implementation of an efficient priority queue","volume":"10","author":"VAN EMDE BOAS P.","year":"1977","journal-title":"Math. Syst. Theory"},{"key":"e_1_2_1_35_2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1287\/mnsc.21.1.87","article-title":"A primal algorithm to solve network flow problems with convex costs","volume":"21","author":"WEINTRAUB A","year":"1974","journal-title":"Manage. Sci."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/76359.76368","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T10:22:22Z","timestamp":1614853342000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,10]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1989,10]]}},"alternative-id":["10.1145\/76359.76368"],"URL":"http:\/\/dx.doi.org\/10.1145\/76359.76368","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1989,10]]}}}