{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:42:29Z","timestamp":1787017349661,"version":"build-2736575974"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"12","license":[{"start":{"date-parts":[[2024,11,17]],"date-time":"2024-11-17T00:00:00Z","timestamp":1731801600000},"content-version":"vor","delay-in-days":366,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2106444,CCF-1844855,CCF-1955039,CCF-1846218"],"award-info":[{"award-number":["CCF-2106444,CCF-1844855,CCF-1955039,CCF-1846218"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200021 204787"],"award-info":[{"award-number":["200021 204787"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Ontario Early Researcher Award","award":["ER21-16-283"],"award-info":[{"award-number":["ER21-16-283"]}]},{"name":"NSERC Discovery Grant","award":["RGPIN-2022-03207,RGPIN-2018-06398"],"award-info":[{"award-number":["RGPIN-2022-03207,RGPIN-2018-06398"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:p>\n                    We present an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    edges and polynomially bounded integral demands, costs, and capacities in\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    <jats:sup>\n                      1+\n                      <jats:italic toggle=\"yes\">o<\/jats:italic>\n                      (1)\n                    <\/jats:sup>\n                    time. Our algorithm builds the flow through a sequence of\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    <jats:sup>\n                      1+\n                      <jats:italic toggle=\"yes\">o<\/jats:italic>\n                      (1)\n                    <\/jats:sup>\n                    approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    <jats:sup>\n                      <jats:italic toggle=\"yes\">o<\/jats:italic>\n                      (1)\n                    <\/jats:sup>\n                    time using a new dynamic graph data structure.\n                  <\/jats:p>\n                  <jats:p>\n                    Our framework extends to algorithms running in\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    <jats:sup>\n                      1+\n                      <jats:italic toggle=\"yes\">o<\/jats:italic>\n                      (1)\n                    <\/jats:sup>\n                    time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling,\n                    <jats:italic toggle=\"yes\">p<\/jats:italic>\n                    -norm flows, and\n                    <jats:italic toggle=\"yes\">p<\/jats:italic>\n                    -norm isotonic regression on arbitrary directed acyclic graphs.\n                  <\/jats:p>","DOI":"10.1145\/3610940","type":"journal-article","created":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T10:06:08Z","timestamp":1700215568000},"page":"85-92","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow"],"prefix":"10.1145","volume":"66","author":[{"given":"Li","family":"Chen","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rasmus","family":"Kyng","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yang P.","family":"Liu","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maximilian Probst","family":"Gutenberg","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sushant","family":"Sachdeva","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,11,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00088"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1115575"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00018"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00059"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00100"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00063"},{"key":"e_1_2_1_8_1","volume-title":"STOC","author":"Brand J.v.d.","year":"2021","unstructured":"Brand, J.v.d., Lee, Y.T., Liu, Y.P., Saranurak, T., Sidford, A., Song, Z., et al. Minimum cost flows, mdps, and \u21131-regression in nearly linear time for dense instances. In STOC (2021), ACM, NY, 859--869."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00090"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384309"},{"key":"e_1_2_1_11_1","volume-title":"2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)","author":"Cen R.","year":"2021","unstructured":"Cen, R., Li, J., Nanongkai, D., Panigrahi, D., Saranurak, T., Quanrud, K. Minimum cuts in directed graphs via partial sparsification. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (2021), IEEE, Denver, CO, 1147--1158."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_2_1_14_1","volume-title":"Application of the simplex method to a transportation problem","author":"Dantzig G.B.","year":"1951","unstructured":"Dantzig, G.B. Application of the simplex method to a transportation problem. In Activity Analysis and Production and Allocation, T.C. Koopmans (ed.), (1951), John Wiley and Sons, New York, 359--373."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00058"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.15.3.430"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808695"},{"key":"e_1_2_1_21_1","first-page":"81","article-title":"On finding maximum flows in networks with special structure and some applications","volume":"5","author":"Karzanov A.V","year":"1973","unstructured":"Karzanov, A.V. On finding maximum flows in networks with special structure and some applications. Matematicheskie Voprosy Upravleniya Proizvodstvom 5, (1973), 81--94.","journal-title":"Matematicheskie Voprosy Upravleniya Proizvodstvom"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00020"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634090"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316410"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451088"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451112"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384247"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.70"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (2016","author":"Peng R.","year":"1862","unstructured":"Peng, R. Approximate undirected maximum flows in o(mpolylog(n)) time. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (2016), SIAM, Philadelphia, PA, 1862--1867."},{"key":"e_1_2_1_31_1","first-page":"1","article-title":"A polynomial-time algorithm, based on newton's method, for linear programming","volume":"40","author":"Renegar J","year":"1988","unstructured":"Renegar, J. A polynomial-time algorithm, based on newton's method, for linear programming. Math. Program. 40, 1 (1988), 59--93.","journal-title":"Math. Program."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.36"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055501"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520068"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3610940","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3610940","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3610940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T18:29:00Z","timestamp":1755973740000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3610940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,17]]},"references-count":35,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10.1145\/3610940"],"URL":"https:\/\/doi.org\/10.1145\/3610940","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,17]]},"assertion":[{"value":"2023-11-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}