{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T18:46:33Z","timestamp":1754160393424,"version":"3.41.2"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"National Science Foundation","award":["CCF-1846218"],"award-info":[{"award-number":["CCF-1846218"]}]},{"name":"NSF","award":["CCF-1749609, DMS-1839116, DMS-2023166, CCF-2105772"],"award-info":[{"award-number":["CCF-1749609, DMS-1839116, DMS-2023166, CCF-2105772"]}]},{"name":"Microsoft Research Faculty Fellowship, a Sloan Research Fellowship, and a Packard Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,8,31]]},"abstract":"<jats:p>\n            We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially-bounded integer costs and capacities. The previous fastest algorithm for this problem is based on interior point methods (IPMs) and works for general sparse graphs in\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            <jats:sup>1.5<\/jats:sup>\n            \u22c5 poly (log\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            )) time [Daitch-Spielman, STOC\u201908].\n          <\/jats:p>\n          <jats:p>\n            Intuitively, \u03a9 (\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            <jats:sup>1.5<\/jats:sup>\n            ) is a natural runtime barrier for IPM-based methods, since they require\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\sqrt {n}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            iterations, each routing a possibly-dense electrical flow. To break this barrier, we develop a new implicit representation for flows based on generalized nested dissection [Lipton-Rose-Tarjan, SINUM\u201979] and approximate Schur complements [Kyng-Sachdeva, FOCS\u201916]. This implicit representation permits us to design a data structure to route an electrical flow with sparse demands in roughly\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\sqrt {n}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            update time, resulting in a total runtime of\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            \u22c5 poly (log\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            )).\n          <\/jats:p>\n          <jats:p>Our results immediately extend to all families of separable graphs.<\/jats:p>","DOI":"10.1145\/3744639","type":"journal-article","created":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T06:49:34Z","timestamp":1749883774000},"page":"1-75","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-5238-648X","authenticated-orcid":false,"given":"Sally","family":"Dong","sequence":"first","affiliation":[{"name":"Paul G Allen School of Computer Science and Engineering, University of Washington","place":["Seattle, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-4660-2149","authenticated-orcid":false,"given":"Yu","family":"Gao","sequence":"additional","affiliation":[{"name":"School of Computer Science, Georgia Institute of Technology","place":["Atlanta, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9603-2255","authenticated-orcid":false,"given":"Gramoz","family":"Goranci","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, University of Vienna","place":["Vienna, Austria"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4692-5442","authenticated-orcid":false,"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"Paul G Allen School of Computer Science and Engineering, University of Washington","place":["Seattle, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5393-9324","authenticated-orcid":false,"given":"Sushant","family":"Sachdeva","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Toronto","place":["Toronto, Canada"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5407-7965","authenticated-orcid":false,"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Computer Science Department, Carnegie Mellon University","place":["Pittsburgh, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1197-0649","authenticated-orcid":false,"given":"Guanghao","family":"Ye","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology","place":["Cambridge, United States"]}]}],"member":"320","published-online":{"date-parts":[[2025,7,26]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"9:1\u20139:15","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming","author":"Adil Deeksha","year":"2021","unstructured":"Deeksha Adil, Brian Bullins, Rasmus Kyng, and Sushant Sachdeva. 2021. Almost-linear-time weighted \\(\\ell _p\\) -norm solvers in slightly dense graphs via sparsification. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 9:1\u20139:15."},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"1405","DOI":"10.1137\/1.9781611975482.86","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Adil Deeksha","year":"2019","unstructured":"Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva. 2019. Iterative refinement for \\(p\\) -norm regression. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. Timothy M. Chan (Ed.), SIAM, 1405\u20131424. DOi:10.1137\/1.9781611975482.86"},{"key":"e_1_3_3_4_2","first-page":"892","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Adil Deeksha","year":"2020","unstructured":"Deeksha Adil and Sushant Sachdeva. 2020. Faster \\(p\\) -norm minimizing flows, via smoothed \\(q\\) -norm problems. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 892\u2013910."},{"key":"e_1_3_3_5_2","doi-asserted-by":"crossref","DOI":"10.21236\/ADA594171","volume-title":"Network Flows","author":"Ahuja Ravindra K.","year":"1988","unstructured":"Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1988. Network Flows. Prentice Hall."},{"key":"e_1_3_3_6_2","first-page":"457","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Asathulla Mudabir Kabir","year":"2018","unstructured":"Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, and Sharath Raghvendra. 2018. A faster algorithm for minimum-cost bipartite perfect matching in planar graphs. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 457\u2013476."},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/FOCS46700.2020.00018","volume-title":"Proceedings of the 2020 IEEE 61st Annual Symposium on Foundations of Computer Science","author":"Axiotis Kyriakos","year":"2020","unstructured":"Kyriakos Axiotis, Aleksander M\u0105dry, and Adrian Vladu. 2020. Circulation control for faster minimum cost flow in unit-capacity graphs. In Proceedings of the 2020 IEEE 61st Annual Symposium on Foundations of Computer Science. IEEE, 93\u2013104."},{"key":"e_1_3_3_8_2","volume-title":"Proceedings of the 62st IEEE Annual Symposium on Foundations of Computer Science","author":"Bernstein Aaron","year":"2021","unstructured":"Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. 2021. Deterministic decremental SSSP and approximate min-cost flow in almost-linear time. In Proceedings of the 62st IEEE Annual Symposium on Foundations of Computer Science. IEEE."},{"key":"e_1_3_3_9_2","volume-title":"Exploiting Planarity for Network Flow and Connectivity Problems","author":"Borradaile Glencora","year":"2008","unstructured":"Glencora Borradaile. 2008. Exploiting Planarity for Network Flow and Connectivity Problems. Brown University."},{"issue":"2","key":"e_1_3_3_10_2","first-page":"9:1\u20139:30","article-title":"An  \\({O}(n \\log {n})\\)  algorithm for maximum st-flow in a directed planar graph","volume":"56","author":"Borradaile Glencora","year":"2009","unstructured":"Glencora Borradaile and Philip N. Klein. 2009. An \\({O}(n \\log {n})\\) algorithm for maximum st-flow in a directed planar graph. Journal of the ACM 56, 2 (2009), 9:1\u20139:30.","journal-title":"Journal of the ACM"},{"issue":"4","key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"1280","DOI":"10.1137\/15M1042929","article-title":"Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time","volume":"46","author":"Borradaile Glencora","year":"2017","unstructured":"Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. 2017. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. SIAMJournal on Computing 46, 4 (2017), 1280\u20131303.","journal-title":"SIAMJournal on Computing"},{"issue":"6","key":"e_1_3_3_12_2","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1137\/090766863","article-title":"Homology flows, cohomology cuts","volume":"41","author":"Chambers Erin W.","year":"2012","unstructured":"Erin W. Chambers, Jeff Erickson, and Amir Nayyeri. 2012. Homology flows, cohomology cuts. SIAMJournal on Computing 41, 6 (2012), 1605\u20131634.","journal-title":"SIAMJournal on Computing"},{"key":"e_1_3_3_13_2","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1109\/FOCS54457.2022.00064","volume-title":"Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science","author":"Chen Li","year":"2022","unstructured":"Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. 2022. Maximum flow and minimum-cost flow in almost-linear time. In Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science. IEEE, 612\u2013623."},{"key":"e_1_3_3_14_2","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1145\/1993636.1993674","volume-title":"Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing","author":"Christiano Paul","year":"2011","unstructured":"Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. 2011. Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing. 273\u2013282."},{"issue":"1","key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3424305","article-title":"Solving linear programs in the current matrix multiplication time","volume":"68","author":"Cohen Michael B.","year":"2021","unstructured":"Michael B. Cohen, Yin Tat Lee, and Zhao Song. 2021. Solving linear programs in the current matrix multiplication time. Journal of the ACM 68, 1 (2021), 1\u201339.","journal-title":"Journal of the ACM"},{"key":"e_1_3_3_16_2","first-page":"752","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Cohen Michael B.","year":"2017","unstructured":"Michael B. Cohen, Aleksander M\u0105dry, Piotr Sankowski, and Adrian Vladu. 2017. Negative-weight shortest paths and unit capacity minimum cost flow in \\(\\widetilde{O}(m^{10\/7} \\log W)\\) time. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 752\u2013771."},{"key":"e_1_3_3_17_2","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms. MIT Press."},{"key":"e_1_3_3_18_2","first-page":"451","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing","author":"Daitch Samuel I.","year":"2008","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. 451\u2013460."},{"key":"e_1_3_3_19_2","volume-title":"Convex Optimization with Combinatorial Characteristics: New Algorithms for Linear Programming, Min-cost Flow, and Other Structured Problems","author":"Dong Sally","year":"2024","unstructured":"Sally Dong. 2024. Convex Optimization with Combinatorial Characteristics: New Algorithms for Linear Programming, Min-cost Flow, and Other Structured Problems. Ph.D. Dissertation. University of Washington."},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"3558","DOI":"10.1137\/1.9781611977912.127","volume-title":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Dong Sally","year":"2024","unstructured":"Sally Dong, Gramoz Goranci, Lawrence Li, Sushant Sachdeva, and Guanghao Ye. 2024. Fast algorithms for separable linear programs. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 3558\u20133604."},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","first-page":"1784","DOI":"10.1145\/3406325.3451056","volume-title":"Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201921)","author":"Dong Sally","year":"2021","unstructured":"Sally Dong, Yin Tat Lee, and Guanghao Ye. 2021. A nearly-linear time algorithm for linear programs with small treewidth: A multiscale representation of robust central path. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201921). ACM, 1784\u20131797."},{"key":"e_1_3_3_22_2","unstructured":"Sally Dong Yin Tat Lee and Guanghao Ye. 2021. A nearly-linear time algorithm for linear programs with small treewidth: A multiscale representation of robust central path. arXiv:2011.05365v2. Retrieved from https:\/\/arxiv.org\/abs\/2011.05365v2"},{"key":"e_1_3_3_23_2","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1145\/3055399.3055499","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing","author":"Durfee David","year":"2017","unstructured":"David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva. 2017. Sampling random spanning trees faster than matrix multiplication. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 730\u2013742."},{"issue":"5","key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1016\/j.jcss.2005.05.007","article-title":"Planar graphs, negative weight edges, shortest paths, and near linear time","volume":"72","author":"Fakcharoenphol Jittat","year":"2006","unstructured":"Jittat Fakcharoenphol and Satish Rao. 2006. Planar graphs, negative weight edges, shortest paths, and near linear time. Journal of Computer and System Sciences 72, 5 (2006), 868\u2013889.","journal-title":"Journal of Computer and System Sciences"},{"key":"e_1_3_3_25_2","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","article-title":"Maximal flow through a network","volume":"8","author":"Ford Lester R.","year":"1956","unstructured":"Lester R. Ford and Delbert R. Fulkerson. 1956. Maximal flow through a network. Canadian Journal of Mathematics 8 (1956), 399\u2013404.","journal-title":"Canadian Journal of Mathematics"},{"key":"e_1_3_3_26_2","volume-title":"Proceedings of the 62st IEEE Annual Symposium on Foundations of Computer Science","author":"Gao Yu","year":"2021","unstructured":"Yu Gao, Yang P. Liu, and Richard Peng. 2021. Fully dynamic electrical flows: Sparse maxflow faster than goldberg-rao. In Proceedings of the 62st IEEE Annual Symposium on Foundations of Computer Science. IEEE."},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"2059","DOI":"10.1109\/FOCS57990.2023.00125","volume-title":"Proceedings of the 2023 IEEE 64th Annual Symposium on Foundations of Computer Science","author":"Ghadiri Mehrdad","year":"2023","unstructured":"Mehrdad Ghadiri, Richard Peng, and Santosh S. Vempala. 2023. The bit complexity of efficient continuous optimization. In Proceedings of the 2023 IEEE 64th Annual Symposium on Foundations of Computer Science. IEEE, 2059\u20132070."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396660"},{"key":"e_1_3_3_29_2","series-title":"LIPIcs","first-page":"40:1\u201340:15","volume-title":"Proceedings of the 26th Annual European Symposium on Algorithms","author":"Goranci Gramoz","year":"2018","unstructured":"Gramoz Goranci, Monika Henzinger, and Pan Peng. 2018. Dynamic effective resistances and approximate schur complement on separable graphs. In Proceedings of the 26th Annual European Symposium on Algorithms(LIPIcs\u201918). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 40:1\u201340:15."},{"key":"e_1_3_3_30_2","volume-title":"Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems","author":"Gremban Keith D.","year":"1996","unstructured":"Keith D. Gremban. 1996. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. Ph.D. Dissertation. Carnegie Mellon University."},{"issue":"3","key":"e_1_3_3_31_2","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0020-0190(81)90120-4","article-title":"Maximum flow in  \\((s,t)\\)  planar networks","volume":"13","author":"Hassin Refael","year":"1981","unstructured":"Refael Hassin. 1981. Maximum flow in \\((s,t)\\) planar networks. Information Processing Letters 13, 3 (1981), 107.","journal-title":"Information Processing Letters"},{"issue":"3","key":"e_1_3_3_32_2","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1137\/0214045","article-title":"An O \\((n \\log ^2n)\\)  algorithm for maximum flow in undirected planar networks","volume":"14","author":"Hassin Refael","year":"1985","unstructured":"Refael Hassin and Donald B. Johnson. 1985. An O \\((n \\log ^2n)\\) algorithm for maximum flow in undirected planar networks. SIAM Journal on Computing 14, 3 (1985), 612\u2013624.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"e_1_3_3_33_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1997.1493","article-title":"Faster shortest-path algorithms for planar graphs","volume":"55","author":"Henzinger Monika R.","year":"1997","unstructured":"Monika R. Henzinger, Philip Klein, Satish Rao, and Sairam Subramanian. 1997. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences 55, 1 (1997), 3\u201323.","journal-title":"Journal of Computer and System Sciences"},{"key":"e_1_3_3_34_2","unstructured":"Baihe Huang Shunhua Jiang Zhao Song and Runzhou Tao. 2021. Solving tall dense SDPs in the current matrix multiplication time. arXiv:2101.08208. Retrieved from https:\/\/arxiv.org\/abs\/2101.08208"},{"key":"e_1_3_3_35_2","first-page":"21","volume-title":"Proceedings of the Algorithms, International Symposium SIGAL\u201990 (Lecture Notes in Computer Science)","author":"Imai Hiroshi","year":"1990","unstructured":"Hiroshi Imai and Kazuo Iwano. 1990. Efficient sequential and parallel algorithms for planar minimum cost flow. In Proceedings of the Algorithms, International Symposium SIGAL\u201990 (Lecture Notes in Computer Science). Springer, 21\u201330."},{"issue":"2","key":"e_1_3_3_36_2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0208012","article-title":"Maximum flow in planar networks","volume":"8","author":"Itai Alon","year":"1979","unstructured":"Alon Itai and Yossi Shiloach. 1979. Maximum flow in planar networks. SIAM Journal on Computing 8, 2 (1979), 135\u2013150.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_3_37_2","first-page":"313","volume-title":"Proceedings of the 43rd ACM Symposium on Theory of Computing","author":"Italiano Giuseppe F.","year":"2011","unstructured":"Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. 2011. Improved algorithms for min cut and max flow in undirected planar graphs. In Proceedings of the 43rd ACM Symposium on Theory of Computing. ACM, 313\u2013322."},{"key":"e_1_3_3_38_2","unstructured":"Donggu Kang and James Payor. 2015. Flow rounding. arXiv:1507.08139. Retrieved from https:\/\/arxiv.org\/abs\/1507.08139"},{"key":"e_1_3_3_39_2","unstructured":"Haim Kaplan and Yahav Nussbaum. 2013. Min-cost flow duality in planar networks. arXiv:1306.6728. Retrieved from https:\/\/arxiv.org\/abs\/1306.6728"},{"key":"e_1_3_3_40_2","series-title":"LIPIcs","first-page":"66:1\u201366:17","volume-title":"Proceedings of the 27th Annual European Symposium on Algorithms","author":"Karczmarz Adam","year":"2019","unstructured":"Adam Karczmarz and Piotr Sankowski. 2019. Min-cost flow in unit-capacity planar graphs. In Proceedings of the 27th Annual European Symposium on Algorithms(LIPIcs\u201919). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 66:1\u201366:17."},{"key":"e_1_3_3_41_2","first-page":"119","volume-title":"Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science","author":"Kathuria Tarun","year":"2020","unstructured":"Tarun Kathuria, Yang P. Liu, and Aaron Sidford. 2020. Unit capacity maxflow in almost \\(O(m^{4\/3})\\) time. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science. 119\u2013130. DOI:10.1109\/FOCS46700.2020.00020"},{"key":"e_1_3_3_42_2","first-page":"217","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Kelner Jonathan A.","year":"2014","unstructured":"Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. 2014. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 217\u2013226."},{"key":"e_1_3_3_43_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."},{"issue":"3","key":"e_1_3_3_44_2","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0406038","article-title":"The lattice structure of flow in planar graphs","volume":"6","author":"Khuller Samir","year":"1993","unstructured":"Samir Khuller, Joseph Naor, and Philip Klein. 1993. The lattice structure of flow in planar graphs. SIAM Journal on Discrete Mathematics 6, 3 (1993), 477\u2013490.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"3","key":"e_1_3_3_45_2","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1006\/jagm.1994.1044","article-title":"A faster deterministic maximum flow algorithm","volume":"17","author":"King Valerie","year":"1994","unstructured":"Valerie King, Satish Rao, and Rorbert Tarjan. 1994. A faster deterministic maximum flow algorithm. Journal of Algorithms 17, 3 (1994), 447\u2013474.","journal-title":"Journal of Algorithms"},{"key":"e_1_3_3_46_2","volume-title":"Approximate Gaussian Elimination","author":"Kyng Rasmus","year":"2017","unstructured":"Rasmus Kyng. 2017. Approximate Gaussian Elimination. Ph.D. Dissertation. Yale University."},{"key":"e_1_3_3_47_2","first-page":"842","volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing","author":"Kyng Rasmus","year":"2016","unstructured":"Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. 2016. Sparsified Cholesky and multigrid solvers for connection laplacians. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 842\u2013850."},{"key":"e_1_3_3_48_2","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1145\/3313276.3316410","volume-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing","author":"Kyng Rasmus","year":"2019","unstructured":"Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang. 2019. Flows in almost linear time via adaptive preconditioning. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 902\u2013913."},{"key":"e_1_3_3_49_2","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1109\/FOCS.2016.68","volume-title":"Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science","author":"Kyng Rasmus","year":"2016","unstructured":"Rasmus Kyng and Sushant Sachdeva. 2016. Approximate gaussian elimination for Laplacians\u2014fast, sparse, and simple. In Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science. IEEE, 573\u2013582."},{"key":"e_1_3_3_50_2","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1137\/1.9781611975482.36","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Lahn Nathaniel","year":"2019","unstructured":"Nathaniel Lahn and Sharath Raghvendra. 2019. A faster algorithm for minimum-cost bipartite matching in minor-free graphs. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 569\u2013588."},{"issue":"2","key":"e_1_3_3_51_2","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","article-title":"A planar separator theorem","volume":"36","author":"Lipton R. J.","year":"1979","unstructured":"R. J. Lipton and Robert Tarjan. 1979. A planar separator theorem. SIAM Journal of Applied Mathematics 36, 2 (1979), 177\u2013189.","journal-title":"SIAM Journal of Applied Mathematics"},{"issue":"2","key":"e_1_3_3_52_2","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","article-title":"Generalized nested dissection","volume":"16","author":"Lipton Richard J.","year":"1979","unstructured":"Richard J. Lipton, Donald J. Rose, and Robert Endre Tarjan. 1979. Generalized nested dissection. SIAM Journal on Numerical Analysis 16, 2 (1979), 346\u2013358.","journal-title":"SIAM Journal on Numerical Analysis"},{"key":"e_1_3_3_53_2","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1109\/FOCS.2013.35","volume-title":"Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science","author":"Madry Aleksander","year":"2013","unstructured":"Aleksander Madry. 2013. Navigating central path with electrical flows: From flows to matchings, and back. In Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE, 253\u2013262."},{"key":"e_1_3_3_54_2","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1109\/FOCS.2016.70","volume-title":"Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science","author":"Madry Aleksander","year":"2016","unstructured":"Aleksander Madry. 2016. Computing maximum flow with augmenting electrical flows. In Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science. IEEE, 593\u2013602."},{"issue":"5","key":"e_1_3_3_55_2","doi-asserted-by":"crossref","first-page":"1002","DOI":"10.1137\/S0097539789162997","article-title":"Flow in planar graphs with multiple sources and sinks","volume":"24","author":"Miller Gary L.","year":"1995","unstructured":"Gary L. Miller and Joseph Naor. 1995. Flow in planar graphs with multiple sources and sinks. SIAM Journal on Computing 24, 5 (1995), 1002\u20131017.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_3_56_2","first-page":"1151","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Miller Gary L.","year":"2013","unstructured":"Gary L. Miller and Richard Peng. 2013. Approximate maximum flow on separable undirected graphs. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1151\u20131170."},{"key":"e_1_3_3_57_2","first-page":"377","volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing","author":"Orlin James","year":"1988","unstructured":"James Orlin. 1988. A faster strongly polynomial minimum cost flow algorithm. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing. 377\u2013387."},{"issue":"1","key":"e_1_3_3_58_2","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1137\/0212005","article-title":"Minimum  \\(s\\) - \\(t\\)  cut of a planar undirected network in  \\({O}(n \\log ^2 n)\\)  time","volume":"12","author":"Reif John H.","year":"1983","unstructured":"John H. Reif. 1983. Minimum \\(s\\) - \\(t\\) cut of a planar undirected network in \\({O}(n \\log ^2 n)\\) time. SIAM Journal on Computing 12, 1 (1983), 71\u201381.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_3_59_2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1109\/FOCS.2013.36","volume-title":"Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science","author":"Sherman Jonah","year":"2013","unstructured":"Jonah Sherman. 2013. Nearly maximum flows in nearly linear time. In Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE, 263\u2013269."},{"key":"e_1_3_3_60_2","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1145\/3055399.3055501","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing","author":"Sherman Jonah","year":"2017","unstructured":"Jonah Sherman. 2017. Area-convexity, linf regularization, and undirected multicommodity flow. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 452\u2013460."},{"key":"e_1_3_3_61_2","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1109\/FOCS.2018.00091","volume-title":"Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science","author":"Sidford Aaron","year":"2018","unstructured":"Aaron Sidford and Kevin Tian. 2018. Coordinate methods for accelerating linf regression and faster approximate maximum flow. In Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science. IEEE, 922\u2013933."},{"key":"e_1_3_3_62_2","first-page":"81","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"Spielman Daniel A.","year":"2004","unstructured":"Daniel A. Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing. 81\u201390."},{"key":"e_1_3_3_63_2","volume-title":"An Efficient Planarity Algorithm","author":"Tarjan Robert E.","year":"1971","unstructured":"Robert E. Tarjan. 1971. An Efficient Planarity Algorithm. Technical Report."},{"issue":"6","key":"e_1_3_3_64_2","doi-asserted-by":"crossref","first-page":"1681","DOI":"10.1287\/opre.1100.0846","article-title":"Fast algorithms for specially structured minimum cost flow problems with applications","volume":"58","author":"Vaidyanathan Balachandran","year":"2010","unstructured":"Balachandran Vaidyanathan and Ravindra K. Ahuja. 2010. Fast algorithms for specially structured minimum cost flow problems with applications. Operations Research 58, 6 (2010), 1681\u20131696.","journal-title":"Operations Research"},{"key":"e_1_3_3_65_2","first-page":"259","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Brand Jan van den","year":"2020","unstructured":"Jan van den Brand. 2020. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 259\u2013278."},{"key":"e_1_3_3_66_2","first-page":"1","volume-title":"Proceedings of the Symposium on Simplicity in Algorithms","author":"Brand Jan van den","year":"2021","unstructured":"Jan van den Brand. 2021. Unifying matrix data structures: Simplifying and speeding up iterative algorithms. In Proceedings of the Symposium on Simplicity in Algorithms. SIAM, 1\u201313."},{"key":"e_1_3_3_67_2","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1145\/3519935.3520068","volume-title":"Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing","author":"Brand Jan van den","year":"2022","unstructured":"Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford. 2022. Faster maxflow via improved dynamic spectral vertex sparsifiers. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. 543\u2013556."},{"key":"e_1_3_3_68_2","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1145\/3406325.3451108","volume-title":"Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing","author":"Brand Jan van den","year":"2021","unstructured":"Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. 2021. Minimum cost flows, MDPs, and \\(\\ell 1\\) -regression in nearly linear time for dense instances. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 859\u2013869."},{"key":"e_1_3_3_69_2","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1145\/3357713.3384309","volume-title":"Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing","author":"Brand Jan van den","year":"2020","unstructured":"Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song. 2020. Solving tall dense linear programs in nearly linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. 775\u2013788."},{"issue":"1","key":"e_1_3_3_70_2","first-page":"1","article-title":"\\(Lx= b\\)  Laplacian solvers and their algorithmic applications","volume":"8","author":"Vishnoi Nisheeth K.","year":"2013","unstructured":"Nisheeth K. Vishnoi. 2013. \\(Lx= b\\) Laplacian solvers and their algorithmic applications. Foundations and Trends in Theoretical Computer Science 8, 1\u20132 (2013), 1\u2013141.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"issue":"3","key":"e_1_3_3_71_2","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1006\/jcss.1997.1538","article-title":"Maximum  \\((s, t)\\) -flows in planar networks in  \\({O} (|V| \\log |V|)\\)  time","volume":"55","author":"Weihe Karsten","year":"1997","unstructured":"Karsten Weihe. 1997. Maximum \\((s, t)\\) -flows in planar networks in \\({O} (|V| \\log |V|)\\) time. Journal of Computer and System Sciences 55, 3 (1997), 454\u2013475.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3744639","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,26]],"date-time":"2025-07-26T14:06:53Z","timestamp":1753538813000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3744639"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,26]]},"references-count":70,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,31]]}},"alternative-id":["10.1145\/3744639"],"URL":"https:\/\/doi.org\/10.1145\/3744639","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2025,7,26]]},"assertion":[{"value":"2022-08-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-30","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}