{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:06:42Z","timestamp":1775282802762,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":21,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"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":[[2012,5,19]]},"DOI":"10.1145\/2213977.2213979","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Faster approximate multicommodity flow using quadratically coupled flows"],"prefix":"10.1145","author":[{"given":"Jonathan A.","family":"Kelner","sequence":"first","affiliation":[{"name":"MIT, Boston, MA, USA"}]},{"given":"Gary L.","family":"Miller","sequence":"additional","affiliation":[{"name":"CMU, Pittsburgh, PA, USA"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"CMU, Pittsburgh, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250823"},{"key":"e_1_3_2_2_2_1","volume-title":"Effective stiffness: Generalizing effective resistance sampling to finite element matrices.CoRR, abs\/cs\/1110.4437","author":"Avron H.","year":"2011","unstructured":"H. Avron and S. Toledo . Effective stiffness: Generalizing effective resistance sampling to finite element matrices.CoRR, abs\/cs\/1110.4437 , 2011 . H. Avron and S. Toledo. Effective stiffness: Generalizing effective resistance sampling to finite element matrices.CoRR, abs\/cs\/1110.4437, 2011."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/206744"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/040611781"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_3_2_2_6_1","volume-title":"Support-graph preconditioners for 2-dimensional trusses. CoRR, abs\/cs\/0703119","author":"Daitch S. I.","year":"2007","unstructured":"S. I. Daitch and D. A. Spielman . Support-graph preconditioners for 2-dimensional trusses. CoRR, abs\/cs\/0703119 , 2007 . S. I. Daitch and D. A. Spielman. Support-graph preconditioners for 2-dimensional trusses. CoRR, abs\/cs\/0703119, 2007."},{"key":"e_1_3_2_2_7_1","volume-title":"Faster approximate lossy generalized flow via interior point algorithms.CoRR, abs\/0803.0988","author":"Daitch S. I.","year":"2008","unstructured":"S. I. Daitch and D. A. Spielman . Faster approximate lossy generalized flow via interior point algorithms.CoRR, abs\/0803.0988 , 2008 . S. I. Daitch and D. A. Spielman. Faster approximate lossy generalized flow via interior point algorithms.CoRR, abs\/0803.0988, 2008."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796457"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"crossref","DOI":"10.1090\/conm\/001","volume-title":"Markov random fields and their applications","author":"Kindermann R.","year":"1980","unstructured":"R. Kindermann and J. L. Snell . Markov random fields and their applications . American Mathematical Society , Providence, R.I. , 1980 , 1980. R. Kindermann and J. L. Snell. Markov random fields and their applications. American Mathematical Society, Providence, R.I., 1980, 1980."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_3_2_2_12_1","volume-title":"Solving sdd linear systems in time ~O(m lognlog(1\/E)). CoRR, abs\/1102.4842","author":"Koutis I.","year":"2011","unstructured":"I. Koutis , G. L. Miller , and R. Peng . Solving sdd linear systems in time ~O(m lognlog(1\/E)). CoRR, abs\/1102.4842 , 2011 . I. Koutis, G. L. Miller, and R. Peng. Solving sdd linear systems in time ~O(m lognlog(1\/E)). CoRR, abs\/1102.4842, 2011."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1020"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806708"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.6.1121"},{"key":"e_1_3_2_2_16_1","unstructured":"Y. Saad. Iterative Methods for Sparse Linear Systems. http:\/\/www-users.cs.umn.edu\/~saad\/books.html 1996.   Y. Saad. Iterative Methods for Sparse Linear Systems. http:\/\/www-users.cs.umn.edu\/~saad\/books.html 1996."},{"key":"e_1_3_2_2_17_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_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.70844"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63499"},{"key":"e_1_3_2_2_20_1","volume-title":"October","author":"Vaidya P. M.","year":"1991","unstructured":"P. M. Vaidya . Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A talk based on this manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation , October 1991 . P. M. Vaidya. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A talk based on this manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, October 1991."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0914008"}],"event":{"name":"STOC'12: Symposium on Theory of Computing","location":"New York New York USA","acronym":"STOC'12","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2213979","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2213979","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:54Z","timestamp":1750238454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2213979"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":21,"alternative-id":["10.1145\/2213977.2213979","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2213979","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}