{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:06:39Z","timestamp":1775282799829,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":20,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T00:00:00Z","timestamp":1307318400000},"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":[[2011,6,6]]},"DOI":"10.1145\/1993636.1993674","type":"proceedings-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:53:52Z","timestamp":1307361232000},"page":"273-282","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":130,"title":["Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs"],"prefix":"10.1145","author":[{"given":"Paul","family":"Christiano","sequence":"first","affiliation":[{"name":"MIT, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan A.","family":"Kelner","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksander","family":"Madry","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel A.","family":"Spielman","sequence":"additional","affiliation":[{"name":"Yale University, New Haven, CT, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[{"name":"USC, Los Angeles, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,6,6]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Network flows","author":"Ahuja R. K.","year":"1989","unstructured":"R. K. Ahuja , T. L. Magnanti , and J. B. Orlin . Network flows . Elsevier North-Holland, Inc. , New York, NY, USA , 1989 . R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows. Elsevier North-Holland, Inc., New York, NY, USA, 1989."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-0507(05)80118-5"},{"key":"e_1_3_2_2_3_1","unstructured":"S. Arora E. Hazan and S. Kale. The multiplicative weights update method: A meta-algorithm and applications. Available at http:\/\/www.cs.princeton.edu\/arora\/pubs\/MWsurvey.pdf.  S. Arora E. Hazan and S. Kale. The multiplicative weights update method: A meta-algorithm and applications. Available at http:\/\/www.cs.princeton.edu\/arora\/pubs\/MWsurvey.pdf."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_3_2_2_5_1","volume-title":"Randomized approximation schemes for cuts and flows in capacitated graphs. CoRR, cs.DS\/0207078","author":"Bencz\u00far A. A.","year":"2002","unstructured":"A. A. Bencz\u00far and D. R. Karger . Randomized approximation schemes for cuts and flows in capacitated graphs. CoRR, cs.DS\/0207078 , 2002 . A. A. Bencz\u00far and D. R. Karger. Randomized approximation schemes for cuts and flows in capacitated graphs. CoRR, cs.DS\/0207078, 2002."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"e_1_3_2_2_7_1","volume-title":"Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. CoRR, abs\/1010.2921","author":"Christiano P.","year":"2010","unstructured":"P. Christiano , J. A. Kelner , A. Madry , D. A. Spielman , and S.-H. Teng . Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. CoRR, abs\/1010.2921 , 2010 . P. Christiano, J. A. Kelner, A. Madry, D. A. Spielman, and S.-H. Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. CoRR, abs\/1010.2921, 2010."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796457"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"e_1_3_2_2_13_1","first-page":"490","volume-title":"Proceedings of the 9th Annual Symposium on Discrete Algorithms","author":"Karger D. R.","year":"1998","unstructured":"D. R. Karger . Better random sampling algorithms for flows in undirected graphs . In Proceedings of the 9th Annual Symposium on Discrete Algorithms , pages 490 -- 499 , Philadelphia, PA, USA , 1998 . Society for Industrial and Applied Mathematics. D. R. Karger. Better random sampling algorithms for flows in undirected graphs. In Proceedings of the 9th Annual Symposium on Discrete Algorithms, pages 490--499, Philadelphia, PA, USA, 1998. Society for Industrial and Applied Mathematics."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.30"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.20.2.257"},{"key":"e_1_3_2_2_17_1","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization","author":"Schrijver A.","year":"2003","unstructured":"A. Schrijver . Combinatorial Optimization , Volume A. Number 24 in Algorithms and Combinatorics . Springer , 2003 . A. Schrijver. Combinatorial Optimization, Volume A. Number 24 in Algorithms and Combinatorics. Springer, 2003."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.66"},{"key":"e_1_3_2_2_19_1","volume-title":"Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105","author":"Spielman D. A.","year":"2006","unstructured":"D. A. Spielman and S.-H. Teng . Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105 , 2006 . D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105, 2006."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313689"}],"event":{"name":"STOC'11: Symposium on Theory of Computing","location":"San Jose California USA","acronym":"STOC'11","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-third annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993674","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1993636.1993674","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:06:10Z","timestamp":1750244770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,6]]},"references-count":20,"alternative-id":["10.1145\/1993636.1993674","10.1145\/1993636"],"URL":"https:\/\/doi.org\/10.1145\/1993636.1993674","relation":{},"subject":[],"published":{"date-parts":[[2011,6,6]]},"assertion":[{"value":"2011-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}