{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:13:41Z","timestamp":1781345621005,"version":"3.54.1"},"reference-count":26,"publisher":"Elsevier BV","issue":"5","license":[{"start":{"date-parts":[[2000,12,1]],"date-time":"2000-12-01T00:00:00Z","timestamp":975628800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research Letters"],"published-print":{"date-parts":[[2000,12]]},"DOI":"10.1016\/s0167-6377(00)00059-6","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T17:05:54Z","timestamp":1027616754000},"page":"199-207","source":"Crossref","is-referenced-by-count":14,"title":["Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks"],"prefix":"10.1016","volume":"27","author":[{"given":"S.Thomas","family":"McCormick","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Akiyoshi","family":"Shioura","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0167-6377(00)00059-6_BIB1","series-title":"Network Flows \u2013 Theory, Algorithms, and Applications","author":"Ahuja","year":"1993"},{"key":"10.1016\/S0167-6377(00)00059-6_BIB2","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1137\/0218039","article-title":"Note on Weintraub's minimum-cost circulation algorithm","volume":"18","author":"Barahona","year":"1989","journal-title":"SIAM J. Comp."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1002\/net.3230230106","article-title":"Canceling most helpful total cuts for minimum cost network flow","volume":"23","author":"Ervolina","year":"1993","journal-title":"Networks"},{"key":"10.1016\/S0167-6377(00)00059-6_BIB4","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0166-218X(93)90025-J","article-title":"Two strongly polynomial cut canceling algorithms for minimum cost network flow","volume":"46","author":"Ervolina","year":"1993","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB5","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/290179.290181","article-title":"Beyond the flow decomposition barrier","volume":"45","author":"Goldberg","year":"1998","journal-title":"J. ACM"},{"key":"10.1016\/S0167-6377(00)00059-6_BIB6","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","article-title":"A new approach to the maximum flow problem","volume":"35","author":"Goldberg","year":"1988","journal-title":"J. ACM"},{"key":"10.1016\/S0167-6377(00)00059-6_BIB7","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1145\/76359.76368","article-title":"Finding minimum-cost circulations by cancelling negative cycles","volume":"36","author":"Goldberg","year":"1989","journal-title":"J. ACM"},{"key":"10.1016\/S0167-6377(00)00059-6_BIB8","series-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel","year":"1988"},{"key":"10.1016\/S0167-6377(00)00059-6_BIB9","unstructured":"M. Hadjiat, Un algorithme fortement polynomial pour la tension de co\u00fbt minimum bas\u00e9 sur les cocycles de co\u00fbts moyens minimums, Technical Report, Groupe Intelligence Artificielle, Facult\u00e9 des Sciences de Luminy, Marseille France, 1994 (in French)."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB10","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1007\/BF02591772","article-title":"The minimum cost flow problem: a unifying approach to dual algorithms and a new tree-search algorithm","volume":"25","author":"Hassin","year":"1983","journal-title":"Math. Programming"},{"key":"10.1016\/S0167-6377(00)00059-6_BIB11","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1137\/S0097539794263695","article-title":"Polynomial methods for separable convex optimization in unimodular spaces with applications","volume":"26","author":"Karzanov","year":"1997","journal-title":"SIAM J. Comp."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB12","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1287\/mnsc.14.3.205","article-title":"A primal method for minimal cost flows","volume":"14","author":"Klein","year":"1967","journal-title":"Management Sci."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB13","unstructured":"S.T. McCormick, A. Schulz, A. Shioura, R. Weismantel, An oracle-polynomial primal augmentation algorithm for mixed integer programs, manuscript, May 2000."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB14","unstructured":"S.T. McCormick, A. Shioura, A minimum ratio cycle cancelling algorithm for linear programming problems with application to network optimization problems, manuscript, November 1996."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB15","doi-asserted-by":"crossref","first-page":"852","DOI":"10.1145\/2157.322410","article-title":"Applying parallel computation algorithms in the design of serial algorithms","volume":"30","author":"Megiddo","year":"1983","journal-title":"J. ACM"},{"key":"10.1016\/S0167-6377(00)00059-6_BIB16","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1287\/moor.5.2.258","article-title":"Theoretical efficiency of the algorithm \u2018Capacity\u2019 for the maximum flow problem","volume":"5","author":"Queyranne","year":"1980","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB17","series-title":"Complexity in Numerical Optimization","first-page":"351","article-title":"Parametric flows, weighted means of cuts, and fractional combinatorial optimization","author":"Radzik","year":"1993"},{"key":"10.1016\/S0167-6377(00)00059-6_BIB18","series-title":"Network Flows and Monotropic Optimizatiion","author":"Rockafellar","year":"1984"},{"key":"10.1016\/S0167-6377(00)00059-6_BIB19","series-title":"Theory of Linear and Integer Programming","author":"Schrijver","year":"1986"},{"key":"10.1016\/S0167-6377(00)00059-6_BIB20","unstructured":"A.S. Schulz, R. Weismantel, A polynomial-time augmentation algorithm for integer programming, manuscript, Fachbereich Mathmatik, Technische Universit\u00e4t Berlin, 1998."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB21","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1287\/moor.25.1.76.15208","article-title":"Relaxed most negative cycle and most positive cut cancelling algorithms for minimum cost flow","volume":"25","author":"Shigeno","year":"2000","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB22","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","article-title":"A strongly polynomial algorithm to solve combinatorial linear programs","volume":"34","author":"Tardos","year":"1986","journal-title":"Oper. Res."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB23","unstructured":"C. Wallacher, A generalization of the minimum-mean cycle selection rule in cycle cancelling algorithms, unpublished manuscript, Institut f\u00fcr Angewandte Mathematik, Technische Universit\u00e4t Braunschweig, 1989."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB24","doi-asserted-by":"crossref","unstructured":"K. Wayne, A polynomial combinatorial algorithm for generalized minimum cost flow, Proceedings of the 31st Annual ACM Symposium on the Theory of Computing, 1999.","DOI":"10.1145\/301250.301261"},{"key":"10.1016\/S0167-6377(00)00059-6_BIB25","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","year":"1974","journal-title":"Management Sci."},{"key":"10.1016\/S0167-6377(00)00059-6_BIB26","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01580122","article-title":"More pathological examples for network flow problems","volume":"5","author":"Zadeh","year":"1973","journal-title":"Math. Programming"}],"container-title":["Operations Research Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167637700000596?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167637700000596?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T14:28:24Z","timestamp":1555770504000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0167637700000596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,12]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2000,12]]}},"alternative-id":["S0167637700000596"],"URL":"https:\/\/doi.org\/10.1016\/s0167-6377(00)00059-6","relation":{},"ISSN":["0167-6377"],"issn-type":[{"value":"0167-6377","type":"print"}],"subject":[],"published":{"date-parts":[[2000,12]]}}}