{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:34:20Z","timestamp":1792071260641,"version":"4.4.0"},"reference-count":141,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T00:00:00Z","timestamp":1747180800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["CCF-1955039, and CCF-2106444"],"award-info":[{"award-number":["CCF-1955039, and CCF-2106444"]}]},{"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":"NSF CAREER","award":["CCF-1844855, and CCF-1846218"],"award-info":[{"award-number":["CCF-1844855, and CCF-1846218"]}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["RGPIN-2022-03207, and RGPIN-2018-06398"],"award-info":[{"award-number":["RGPIN-2022-03207, and RGPIN-2018-06398"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ERA","award":["ER21-16-283"],"award-info":[{"award-number":["ER21-16-283"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n                    We present an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with\n                    <jats:italic>m<\/jats:italic>\n                    edges and polynomially bounded integral demands, costs, and capacities in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(m^{1+o(1)}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    time. Our algorithm builds the flow through a sequence of\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(m^{1+o(1)}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(m^{o(1)}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\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:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(m^{1+o(1)}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\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>p<\/jats:italic>\n                    -norm flows, and\n                    <jats:italic>p<\/jats:italic>\n                    -norm isotonic regression on arbitrary directed acyclic graphs.\n                  <\/jats:p>","DOI":"10.1145\/3728631","type":"journal-article","created":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T06:02:36Z","timestamp":1744178556000},"page":"1-103","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Maximum Flow and Minimum-Cost Flow in Almost-Linear Time"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2585-6027","authenticated-orcid":false,"given":"Li","family":"Chen","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8268-6258","authenticated-orcid":false,"given":"Rasmus","family":"Kyng","sequence":"additional","affiliation":[{"name":"ETH Zurich Department of Computer Science, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6717-0539","authenticated-orcid":false,"given":"Yang","family":"Liu","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5407-7965","authenticated-orcid":false,"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3522-156X","authenticated-orcid":false,"given":"Maximilian","family":"Probst Gutenberg","sequence":"additional","affiliation":[{"name":"Computer Science, ETH Z\u00fcrich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5393-9324","authenticated-orcid":false,"given":"Sushant","family":"Sachdeva","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,5,14]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00088"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1115575"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2021.9"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.86"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.54"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585705"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.87"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3301"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00018"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00059"},{"key":"e_1_3_4_13_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00224-005-1254-y","article-title":"Matching algorithms are fast in sparse random graphs","volume":"39","author":"Bast Hannah","year":"2004","unstructured":"Hannah Bast, Kurt Mehlhorn, Guido Sch\u00e4fer, and Hisao Tamaki. 2004. Matching algorithms are fast in sparse random graphs. Theory Comput. Syst. 39 (2004), 3\u201314. https:\/\/api.semanticscholar.org\/CorpusID:9321036","journal-title":"Theory Comput. Syst."},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/141000439"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00108"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00100"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2022.20"},{"key":"e_1_3_4_18_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization (1st ed.)","author":"Boyd Stephen","year":"2004","unstructured":"Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization (1st ed.). Cambridge University Press, Cambridge, UK. Retrieved from http:\/\/web.stanford.edu\/boyd\/cvxbook\/."},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.60"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.10.027"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00113"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1287\/OPRE.1080.0572"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00109"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649745"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00060"},{"key":"e_1_3_4_26_2","unstructured":"Sinho Chewi. 2021. The Entropic Barrier is \\(n\\) -self-concordant. Retrieved from https:\/\/arxiv.org\/abs\/2112.10947."},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451025"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316320"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.147"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3424305"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.88"},{"key":"e_1_3_4_33_2","first-page":"2292","volume-title":"Proceedings of the 27th Annual Conference on Neural Information Processing Systems","author":"Cuturi Marco","year":"2013","unstructured":"Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Proceedings of the 27th Annual Conference on Neural Information Processing Systems. 2292\u20132300. Retrieved from https:\/\/proceedings.neurips.cc\/paper\/2013\/hash\/af21d0c97db2e27e13572cbf59eb343d-Abstract.html."},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_4_35_2","series-title":"Cowles Commission Monographs","first-page":"359","volume-title":"Activity Analysis of Production and Allocation","author":"Dantzig George B.","year":"1951","unstructured":"George B. Dantzig. 1951. Application of the simplex method to a transportation problem. In Activity Analysis of Production and Allocation. Cowles Commission Monographs, Vol. No. 13. Wiley, New York, NY, 359\u2013373."},{"key":"e_1_3_4_36_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.","year":"1970","unstructured":"E. A. Dinic. 1970. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Doklady 11 (1970), 1277\u20131280.","journal-title":"Soviet Math. Doklady"},{"key":"e_1_3_4_37_2","article-title":"Metod porazryadnogo sokrashcheniya nevyazok i transportnye zadachi","author":"Dinic E. A.","year":"1973","unstructured":"E. A. Dinic. 1973. Metod porazryadnogo sokrashcheniya nevyazok i transportnye zadachi. Issledovaniya po Diskretno\u01d0 Matematike (1973). In Russian. Title translation: Excess scaling and transportation problems..","journal-title":"Issledovaniya po Diskretno\u01d0 Matematike"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.7"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451056"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3155301"},{"key":"e_1_3_4_41_2","series-title":"Proceedings of Machine Learning Research","first-page":"1366","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML\u201918)","volume":"80","author":"Dvurechensky Pavel E.","year":"2018","unstructured":"Pavel E. Dvurechensky, Alexander V. Gasnikov, and Alexey Kroshnin. 2018. Computational optimal transport: Complexity by accelerated gradient descent is better than by sinkhorn\u2019s algorithm. In Proceedings of the 35th International Conference on Machine Learning (ICML\u201918)(Proceedings of Machine Learning Research, Vol. 80). PMLR, 1366\u20131375. Retrieved from http:\/\/proceedings.mlr.press\/v80\/dvurechensky18a.html."},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1002\/NET.3230230106"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90025-J"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.5"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_3_4_48_2","unstructured":"Barak Fishbain Dorit S. Hochbaum and Stefan Mueller. 2010. Competitive analysis of minimum-cut maximum flow algorithms in vision problems. Retrieved from https:\/\/arxiv.org\/abs\/1007.4531."},{"key":"e_1_3_4_49_2","volume-title":"Maximal Flow through a Network.","author":"Ford L. R.","year":"1954","unstructured":"L. R. Ford and D. R. Fulkerson. 1954. Maximal Flow through a Network.RAND Corporation, Santa Monica, CA."},{"key":"e_1_3_4_50_2","series-title":"Proceedings of Machine Learning Research","first-page":"3222","volume-title":"Proceedings of the 37th International Conference on Machine Learning (ICML\u201920)","volume":"119","author":"Fountoulakis Kimon","year":"2020","unstructured":"Kimon Fountoulakis, Di Wang, and Shenghao Yang. 2020. \\(p\\) -norm flow diffusion for local graph clustering. In Proceedings of the 37th International Conference on Machine Learning (ICML\u201920)(Proceedings of Machine Learning Research, Vol. 119). PMLR, 3222\u20133232. Retrieved from http:\/\/proceedings.mlr.press\/v119\/fountoulakis20a.html."},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/0109002"},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321942"},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90039-X"},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2017-1555"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218069"},{"key":"e_1_3_4_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/115234.115366"},{"key":"e_1_3_4_57_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90035-5"},{"key":"e_1_3_4_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/42282.214090"},{"key":"e_1_3_4_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00058"},{"key":"e_1_3_4_60_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792231179"},{"key":"e_1_3_4_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_39"},{"key":"e_1_3_4_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_52"},{"key":"e_1_3_4_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/S10107-004-0505-Z"},{"key":"e_1_3_4_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"e_1_3_4_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28397"},{"key":"e_1_3_4_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_3_4_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76368"},{"key":"e_1_3_4_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/2628036"},{"key":"e_1_3_4_69_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02288321"},{"key":"e_1_3_4_70_2","series-title":"Proceedings of Machine Learning Research","first-page":"2088","volume-title":"Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS\u201920)","volume":"108","author":"Guo Wenshuo","year":"2020","unstructured":"Wenshuo Guo, Nhat Ho, and Michael I. Jordan. 2020. Fast algorithms for computational optimal transport and wasserstein barycenter. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS\u201920)(Proceedings of Machine Learning Research, Vol. 108). PMLR, 2088\u20132097. http:\/\/proceedings.mlr.press\/v108\/guo20a.html"},{"key":"e_1_3_4_71_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591772"},{"key":"e_1_3_4_72_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90048-8"},{"key":"e_1_3_4_73_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-023-01154-8"},{"key":"e_1_3_4_74_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1180335"},{"key":"e_1_3_4_75_2","doi-asserted-by":"publisher","DOI":"10.5555\/3215127.3215137"},{"key":"e_1_3_4_76_2","doi-asserted-by":"publisher","DOI":"10.1287\/OPRE.1080.0524"},{"key":"e_1_3_4_77_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100369584"},{"key":"e_1_3_4_78_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_4_79_2","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1090\/dimacs\/012","volume-title":"Network Flows And Matching, Proceedings of a DIMACS Workshop","volume":"12","author":"Johnson David S.","year":"1993","unstructured":"David S. Johnson and Catherine C. McGeoch (Eds.). 1993. In Network Flows And Matching, Proceedings of a DIMACS Workshop. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 12. DIMACS\/AMS."},{"key":"e_1_3_4_80_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_3_4_81_2","first-page":"81","article-title":"On finding maximum flows in networks with special structure and some applications","volume":"5","author":"Karzanov Alexander V.","year":"1973","unstructured":"Alexander V. Karzanov. 1973. On finding maximum flows in networks with special structure and some applications. Matematicheskie Voprosy Upravleniya Proizvodstvom 5 (1973), 81\u201394.","journal-title":"Matematicheskie Voprosy Upravleniya Proizvodstvom"},{"key":"e_1_3_4_82_2","first-page":"306","article-title":"Efficient implementations of Edmonds\u2019 algorithms for finding matchings with maximum cardinality and maximum weight","author":"Karzanov Aleksandr V.","year":"1976","unstructured":"Aleksandr V. Karzanov. 1976. Efficient implementations of Edmonds\u2019 algorithms for finding matchings with maximum cardinality and maximum weight. Studies Discrete Optim. (1976), 306\u2013327.","journal-title":"Studies Discrete Optim."},{"key":"e_1_3_4_83_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00020"},{"key":"e_1_3_4_84_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.16"},{"key":"e_1_3_4_85_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213979"},{"key":"e_1_3_4_86_2","first-page":"911","volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing","author":"Kelner Jonathan A.","year":"2013","unstructured":"Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. 2013. A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 911\u2013920."},{"key":"e_1_3_4_87_2","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538903"},{"key":"e_1_3_4_88_2","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2014.895828"},{"key":"e_1_3_4_89_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.EJOR.2011.11.008"},{"key":"e_1_3_4_90_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316410"},{"key":"e_1_3_4_91_2","first-page":"2719","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems","author":"Kyng Rasmus","year":"2015","unstructured":"Rasmus Kyng, Anup Rao, and Sushant Sachdeva. 2015. Fast, provable algorithms for isotonic regression in all \\(L_p\\) -norms. In Proceedings of the Annual Conference on Neural Information Processing Systems. 2719\u20132727. Retrieved from https:\/\/proceedings.neurips.cc\/paper\/2015\/hash\/be53ee61104935234b174e62a07e53cf-Abstract.html."},{"key":"e_1_3_4_92_2","unstructured":"Yin Tat Lee and Aaron Sidford. 2019. Solving linear programs with sqrt (rank) linear system solves. Retrieved from http:\/\/arxiv.org\/abs\/1910.08033."},{"key":"e_1_3_4_93_2","series-title":"Proceedings of Machine Learning Research","first-page":"2140","volume-title":"Proceedings of the Conference on Learning Theory (COLT\u201919)","volume":"99","author":"Lee Yin Tat","year":"2019","unstructured":"Yin Tat Lee, Zhao Song, and Qiuyi Zhang. 2019. Solving empirical risk minimization in the current matrix multiplication time. In Proceedings of the Conference on Learning Theory (COLT\u201919)(Proceedings of Machine Learning Research, Vol. 99). PMLR, 2140\u20132157. Retrieved from http:\/\/proceedings.mlr.press\/v99\/lee19a.html."},{"key":"e_1_3_4_94_2","unstructured":"Yin Tat Lee and Santosh S. Vempala. 2021. Tutorial on the robust interior point method. Retrieved from https:\/\/arxiv.org\/abs\/2108.04734."},{"key":"e_1_3_4_95_2","doi-asserted-by":"publisher","DOI":"10.1287\/MOOR.2020.1113"},{"key":"e_1_3_4_96_2","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_3_4_97_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451088"},{"key":"e_1_3_4_98_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00017"},{"key":"e_1_3_4_99_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451112"},{"key":"e_1_3_4_100_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384247"},{"key":"e_1_3_4_101_2","unstructured":"Anand Louis. 2010. Cut-matching games on directed graphs. Retrieved from https:\/\/arxiv.org\/abs\/1010.1047."},{"key":"e_1_3_4_102_2","doi-asserted-by":"publisher","DOI":"10.1090\/chel\/367"},{"key":"e_1_3_4_103_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.30"},{"key":"e_1_3_4_104_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_3_4_105_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.70"},{"key":"e_1_3_4_106_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"e_1_3_4_107_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.40"},{"key":"e_1_3_4_108_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.92"},{"issue":"16","key":"e_1_3_4_109_2","first-page":"3215","article-title":"Interior point polynomial time methods in convex programming","volume":"42","author":"Nemirovski Arkadi","year":"2004","unstructured":"Arkadi Nemirovski. 2004. Interior point polynomial time methods in convex programming. Lecture Notes 42, 16 (2004), 3215\u20133224. Retrieved from https:\/\/www2.isye.gatech.edu\/nemirovs\/Lect_IPM.pdf.","journal-title":"Lecture Notes"},{"key":"e_1_3_4_110_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0185-1"},{"key":"e_1_3_4_111_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"e_1_3_4_112_2","doi-asserted-by":"publisher","DOI":"10.1287\/OPRE.41.2.338"},{"key":"e_1_3_4_113_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614365"},{"key":"e_1_3_4_114_2","doi-asserted-by":"publisher","DOI":"10.1002\/NET.22001"},{"key":"e_1_3_4_115_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580615"},{"key":"e_1_3_4_116_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.CH130"},{"key":"e_1_3_4_117_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519945"},{"key":"e_1_3_4_118_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90005-9"},{"key":"e_1_3_4_119_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374415"},{"key":"e_1_3_4_120_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580724"},{"key":"e_1_3_4_121_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.162"},{"key":"e_1_3_4_122_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.36"},{"key":"e_1_3_4_123_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055501"},{"key":"e_1_3_4_124_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_4_125_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238215"},{"key":"e_1_3_4_126_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_3_4_127_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-012-9628-4"},{"key":"e_1_3_4_128_2","unstructured":"Quentin F. Stout. 2021. \\(L_{p}\\) isotonic regression algorithms using an \\(L_0\\) approach. Retrieved from https:\/\/arxiv.org\/abs\/2107.00251."},{"key":"e_1_3_4_129_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579369"},{"key":"e_1_3_4_130_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580859"},{"key":"e_1_3_4_131_2","volume-title":"Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201924)","author":"Brand Jan van den","year":"2024","unstructured":"Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, and Sushant Sachdeva. 2024. Almost-linear time algorithms for decremental graphs: Min-cost flow and more via duality. In Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201924)."},{"key":"e_1_3_4_132_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.106"},{"key":"e_1_3_4_133_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00037"},{"key":"e_1_3_4_134_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520068"},{"key":"e_1_3_4_135_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451108"},{"key":"e_1_3_4_136_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00090"},{"key":"e_1_3_4_137_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384309"},{"key":"e_1_3_4_138_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585135"},{"key":"e_1_3_4_139_2","doi-asserted-by":"crossref","unstructured":"Vijay V. Vazirani. 2023. A theory of alternating paths and blossoms from the perspective of minimum length. Math. Oper. Res. 49 3 (2023) 2009\u20132047.","DOI":"10.1287\/moor.2020.0388"},{"key":"e_1_3_4_140_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580905"},{"key":"e_1_3_4_141_2","series-title":"Proceedings of Machine Learning Research","first-page":"3598","volume-title":"Proceedings of the 34th International Conference on Machine Learning (ICML\u201917)","volume":"70","author":"Wang Di","year":"2017","unstructured":"Di Wang, Kimon Fountoulakis, Monika Henzinger, Michael W. Mahoney, and Satish Rao. 2017. Capacity releasing diffusion for speed and locality. In Proceedings of the 34th International Conference on Machine Learning (ICML\u201917)(Proceedings of Machine Learning Research, Vol. 70). PMLR, 3598\u20133607. Retrieved from http:\/\/proceedings.mlr.press\/v70\/wang17b.html."},{"key":"e_1_3_4_142_2","unstructured":"Tianyi Zhang. 2021. Gomory-hu trees in quadratic time. Retrieved from https:\/\/arxiv.org\/abs\/2112.01042."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3728631","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3728631","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:18:36Z","timestamp":1750281516000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3728631"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,14]]},"references-count":141,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3728631"],"URL":"https:\/\/doi.org\/10.1145\/3728631","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,14]]},"assertion":[{"value":"2022-11-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-23","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}