{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:42:44Z","timestamp":1767339764583,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384247","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"803-814","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Faster energy maximization for faster maximum flow"],"prefix":"10.1145","author":[{"given":"Yang P.","family":"Liu","sequence":"first","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.86"},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015","author":"Zhu Zeyuan Allen","year":"2015","unstructured":"Zeyuan Allen Zhu , Zhenyu Liao , and Lorenzo Orecchia . 2015 . Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates . In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015 , Portland, OR, USA , June 14-17, 2015. 237\u2013245. Zeyuan Allen Zhu, Zhenyu Liao, and Lorenzo Orecchia. 2015. Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015. 237\u2013245."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591833"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316303"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039734"},{"key":"e_1_3_2_1_7_1","volume-title":"Ronald L Rivest, and Clifford Stein.","author":"Cormen Thomas H","year":"2001","unstructured":"Thomas H Cormen , Charles Eric Leiserson , Ronald L Rivest, and Clifford Stein. 2001 . Introduction to algorithms. 6, MIT press Cambridge , MA. Thomas H Cormen, Charles Eric Leiserson, Ronald L Rivest, and Clifford Stein. 2001. Introduction to algorithms. 6, MIT press Cambridge, MA."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897654"},{"key":"e_1_3_2_1_10_1","series-title":"SIAM journal on computing, 4, 4","volume-title":"Network flow and testing graph connectivity","author":"Even Shimon","year":"1975","unstructured":"Shimon Even and R Endre Tarjan . 1975. Network flow and testing graph connectivity . SIAM journal on computing, 4, 4 ( 1975 ), 507\u2013518. Shimon Even and R Endre Tarjan. 1975. Network flow and testing graph connectivity. SIAM journal on computing, 4, 4 (1975), 507\u2013518."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218069"},{"key":"e_1_3_2_1_15_1","volume-title":"Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. In 39th Annual Symposium on Foundations of Computer Science, FOCS \u201998","author":"Garg Naveen","year":"1998","unstructured":"Naveen Garg and Jochen K\u00f6nemann . 1998 . Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. In 39th Annual Symposium on Foundations of Computer Science, FOCS \u201998 , November 8-11, 1998, Palo Alto, California, USA. 300\u2013309. Naveen Garg and Jochen K\u00f6nemann. 1998. Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. In 39th Annual Symposium on Foundations of Computer Science, FOCS \u201998, November 8-11, 1998, Palo Alto, California, USA. 300\u2013309."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"e_1_3_2_1_17_1","series-title":"SIAM Journal on computing, 2, 4","volume-title":"An n^5\/2 algorithm for maximum matchings in bipartite graphs","author":"Hopcroft John E","year":"1973","unstructured":"John E Hopcroft and Richard M Karp . 1973. An n^5\/2 algorithm for maximum matchings in bipartite graphs . SIAM Journal on computing, 2, 4 ( 1973 ), 225\u2013231. John E Hopcroft and Richard M Karp. 1973. An n^5\/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2, 4 (1973), 225\u2013231."},{"key":"e_1_3_2_1_18_1","volume-title":"Cut Sparsifiers for Balanced Digraphs. In International Workshop on Approximation and Online Algorithms. 277\u2013294","author":"Ikeda Motoki","year":"2018","unstructured":"Motoki Ikeda and Shin-ichi Tanigawa. 2018 . Cut Sparsifiers for Balanced Digraphs. In International Workshop on Approximation and Online Algorithms. 277\u2013294 . Motoki Ikeda and Shin-ichi Tanigawa. 2018. Cut Sparsifiers for Balanced Digraphs. In International Workshop on Approximation and Online Algorithms. 277\u2013294."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Giuseppe F Italiano and Piotr Sankowski. 2010. Improved minimum cuts and maximum flows in undirected planar graphs. arXiv preprint arXiv:1011.2843.  Giuseppe F Italiano and Piotr Sankowski. 2010. Improved minimum cuts and maximum flows in undirected planar graphs. arXiv preprint arXiv:1011.2843.","DOI":"10.1145\/1993636.1993679"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3226661.3227036"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328924"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2019.66"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258596"},{"key":"e_1_3_2_1_24_1","first-page":"490","article-title":"Better random sampling algorithms for flows in undirected graphs","volume":"98","author":"Karger David R","year":"1998","unstructured":"David R Karger . 1998 . Better random sampling algorithms for flows in undirected graphs . In SODA. 98 , 490 \u2013 499 . David R Karger. 1998. Better random sampling algorithms for flows in undirected graphs. In SODA. 98, 490\u2013499.","journal-title":"SODA."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.2.383"},{"key":"e_1_3_2_1_26_1","first-page":"69","article-title":"Finding maximum flows in undirected graphs seems easier than bipartite matching","volume":"98","author":"Karger David R","year":"1998","unstructured":"David R Karger and Matthew S Levine . 1998 . Finding maximum flows in undirected graphs seems easier than bipartite matching . In STOC. 98 , 69 \u2013 78 . David R Karger and Matthew S Levine. 1998. Finding maximum flows in undirected graphs seems easier than bipartite matching. In STOC. 98, 69\u201378.","journal-title":"STOC."},{"key":"e_1_3_2_1_27_1","unstructured":"Alexander V Karzanov. 1973. O nakhozhdenii maksimal\u2019nogo potoka v setyakh spetsial\u2019nogo vida i nekotorykh prilozheniyakh. Mathematicheskie Voprosy Upravleniya Proizvodstvom.  Alexander V Karzanov. 1973. O nakhozhdenii maksimal\u2019nogo potoka v setyakh spetsial\u2019nogo vida i nekotorykh prilozheniyakh. Mathematicheskie Voprosy Upravleniya Proizvodstvom."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.16"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213979"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.75"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897640"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316410"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.68"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488704"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_1_39_1","volume-title":"Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015","author":"Lee Yin Tat","year":"2015","unstructured":"Yin Tat Lee and Aaron Sidford . 2015 . Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 , Berkeley, CA, USA , 17-20 October, 2015. 230\u2013249. Yin Tat Lee and Aaron Sidford. 2015. Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. 230\u2013249."},{"key":"e_1_3_2_1_40_1","volume-title":"Solving Linear Programs with Sqrt(rank) Linear System Solves. CoRR, abs\/1910.08033","author":"Lee Yin Tat","year":"2019","unstructured":"Yin Tat Lee and Aaron Sidford . 2019. Solving Linear Programs with Sqrt(rank) Linear System Solves. CoRR, abs\/1910.08033 ( 2019 ), arxiv:1910.08033. arxiv:1910.08033 Yin Tat Lee and Aaron Sidford. 2019. Solving Linear Programs with Sqrt(rank) Linear System Solves. CoRR, abs\/1910.08033 (2019), arxiv:1910.08033. arxiv:1910.08033"},{"key":"e_1_3_2_1_41_1","volume-title":"Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015","author":"Lee Yin Tat","year":"2015","unstructured":"Yin Tat Lee and He Sun . 2015 . Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 , Berkeley, CA, USA , 17-20 October, 2015. 250\u2013269. Yin Tat Lee and He Sun. 2015. Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. 250\u2013269."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055477"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806708"},{"key":"e_1_3_2_1_44_1","series-title":"SIAM Journal on optimization, 2, 4","volume-title":"On the implementation of a primal-dual interior point method","author":"Mehrotra Sanjay","year":"1992","unstructured":"Sanjay Mehrotra . 1992. On the implementation of a primal-dual interior point method . SIAM Journal on optimization, 2, 4 ( 1992 ), 575\u2013601. Sanjay Mehrotra. 1992. On the implementation of a primal-dual interior point method. SIAM Journal on optimization, 2, 4 (1992), 575\u2013601."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.70"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.134"},{"key":"e_1_3_2_1_49_1","volume-title":"Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012","author":"Orecchia Lorenzo","year":"2012","unstructured":"Lorenzo Orecchia , Sushant Sachdeva , and Nisheeth K. Vishnoi . 2012. Approximating the exponential, the lanczos method and an \u00d5(m)-time spectral algorithm for balanced separator . In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012 , New York, NY, USA, May 19 - 22 , 2012 . 1141\u20131160. Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi. 2012. Approximating the exponential, the lanczos method and an \u00d5(m)-time spectral algorithm for balanced separator. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012. 1141\u20131160."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch130"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212005"},{"key":"e_1_3_2_1_53_1","first-page":"1","article-title":"A polynomial-time algorithm, based on Newton\u2019s method, for linear programming","volume":"40","author":"Renegar James","year":"1988","unstructured":"James Renegar . 1988 . A polynomial-time algorithm, based on Newton\u2019s method, for linear programming . Math. Program. , 40 , 1 - 3 (1988), 59\u201393. James Renegar. 1988. A polynomial-time algorithm, based on Newton\u2019s method, for linear programming. Math. Program., 40, 1-3 (1988), 59\u201393.","journal-title":"Math. Program."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188852"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.36"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055501"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00091"},{"key":"e_1_3_2_1_58_1","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing","author":"Daniel","year":"2008","unstructured":"Daniel A. Spielman and Nikhil Srivastava. 2008. Graph sparsification by effective resistances . In Proceedings of the 40th Annual ACM Symposium on Theory of Computing , Victoria, British Columbia, Canada , May 17-20, 2008 . 563\u2013568. Daniel A. Spielman and Nikhil Srivastava. 2008. Graph sparsification by effective resistances. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008. 563\u2013568."},{"key":"e_1_3_2_1_59_1","volume-title":"Spielman and Shang-Hua Teng","author":"Daniel","year":"2003","unstructured":"Daniel A. Spielman and Shang-Hua Teng . 2003 . Solving Sparse, Symmetric , Diagonally-Dominant Linear Systems in Time O(m^ 1.31). CoRR , cs.DS\/0310036 (2003), arxiv:cs.DS\/0310036 Daniel A. Spielman and Shang-Hua Teng. 2003. Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O(m^ 1.31). CoRR, cs.DS\/0310036 (2003), arxiv:cs.DS\/0310036"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_3_2_1_61_1","volume-title":"Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A talk based on this manuscript, 2, 3.4","author":"Vaidya Pravin M","year":"1991","unstructured":"Pravin M Vaidya . 1991. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A talk based on this manuscript, 2, 3.4 ( 1991 ), 2\u20134. Pravin M Vaidya. 1991. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A talk based on this manuscript, 2, 3.4 (1991), 2\u20134."},{"key":"e_1_3_2_1_62_1","unstructured":"Christian Wulff-Nilsen. 2010. Min st-Cut of a Planar Graph in O (n loglog n) Time. arXiv preprint arXiv:1007.3609.  Christian Wulff-Nilsen. 2010. Min st-Cut of a Planar Graph in O (n loglog n) Time. arXiv preprint arXiv:1007.3609."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.1.53"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Chicago IL USA","acronym":"STOC '20"},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384247","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384247","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384247"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":63,"alternative-id":["10.1145\/3357713.3384247","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384247","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}