{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T18:33:34Z","timestamp":1792607614500,"version":"4.5.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T00:00:00Z","timestamp":1587081600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M02797X\/1"],"award-info":[{"award-number":["EP\/M02797X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["ScaleOpt?757481"],"award-info":[{"award-number":["ScaleOpt?757481"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["016.Vidi.189.087"],"award-info":[{"award-number":["016.Vidi.189.087"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,4,30]]},"abstract":"<jats:p>\n            We present a new strongly polynomial algorithm for generalized flow maximization that is significantly simpler and faster than the previous strongly polynomial algorithm [34]. For the uncapacitated problem formulation, the complexity bound\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            +\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            )log (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/\n            <jats:italic>m<\/jats:italic>\n            )) improves on the previous estimate by almost a factor\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ). Even for small numerical parameter values, our running time bound is comparable to the best weakly polynomial algorithms. The key new technical idea is relaxing the primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.\n          <\/jats:p>","DOI":"10.1145\/3383454","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T07:14:28Z","timestamp":1588576468000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization"],"prefix":"10.1145","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8897-5459","authenticated-orcid":false,"given":"Neil","family":"Olver","sequence":"first","affiliation":[{"name":"London School of Economics and Political Science, United Kingdom and CWI, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L\u00e1szl\u00f3 A.","family":"V\u00e9gh","sequence":"additional","affiliation":[{"name":"London School of Economics and Political Science, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993","unstructured":"R. K. Ahuja , T. L. Magnanti , and J. B. Orlin . 1993 . Network Flows: Theory, Algorithms, and Applications . Prentice-Hall . R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791256325"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3119414.3119578"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC\u201908)","author":"Samuel","unstructured":"Samuel I. Daitch and Daniel A. Spielman. 2008. Faster approximate lossy generalized flow via interior point algorithms . In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC\u201908) . ACM, 451--460. Samuel I. Daitch and Daniel A. Spielman. 2008. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC\u201908). ACM, 451--460."},{"key":"e_1_2_1_5_1","volume-title":"Linear Programming and Extensions","author":"Dantzig G. B.","unstructured":"G. B. Dantzig . 1963. Linear Programming and Extensions . Princeton University Press , Princeton, NJ . G. B. Dantzig. 1963. Linear Programming and Extensions. Princeton University Press, Princeton, NJ."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100238"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.16.2.351"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76368"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2781835.2781837"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100248"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2786372.2786374"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0333-y"},{"key":"e_1_2_1_14_1","unstructured":"M. Gondran and M. Minoux. 1984. Graphs and Algorithms. John Wiley & Sons New York NY.  M. Gondran and M. Minoux. 1984. Graphs and Algorithms. John Wiley & Sons New York NY."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00074-9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.4.366"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3226661.3227036"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212022"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1966.1082612"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.41.2.338"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00403-1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0183-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113624.3114143"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03025291"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579369"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.34.2.250"},{"key":"e_1_2_1_29_1","first-page":"310","article-title":"Simple maximum flow algorithms in lossy networks. In Proceedings of the Annual Conference on Integer Programming and Combinatorial Optimization (IPCO\u201998)","volume":"1412","author":"Wayne Tardos","year":"1998","unstructured":"\u00c9. Tardos and K. D. Wayne . 1998 . Simple maximum flow algorithms in lossy networks. In Proceedings of the Annual Conference on Integer Programming and Combinatorial Optimization (IPCO\u201998) . Lecture Notes in Computer Science , Vol. 1412. 310 -- 324 . \u00c9. Tardos and K. D. Wayne. 1998. Simple maximum flow algorithms in lossy networks. In Proceedings of the Annual Conference on Integer Programming and Combinatorial Optimization (IPCO\u201998). Lecture Notes in Computer Science, Vol. 1412. 310--324.","journal-title":"Lecture Notes in Computer Science"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63499"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/3114198.3114682"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0623"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/140978296"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0800"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2786397.2786398"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3383454","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3383454","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:22Z","timestamp":1750199602000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3383454"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,17]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,30]]}},"alternative-id":["10.1145\/3383454"],"URL":"https:\/\/doi.org\/10.1145\/3383454","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,17]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}