{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:57:07Z","timestamp":1780073827746,"version":"3.54.0"},"publisher-location":"New York, NY, USA","reference-count":35,"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.3384268","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"308-321","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["Faster parallel algorithm for approximate shortest path"],"prefix":"10.1145","author":[{"given":"Jason","family":"Li","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"406","volume-title":"Proceedings of the forty-fourth annual ACM symposium on Theory of computing","author":"Abraham Ittai","unstructured":"Ittai Abraham and Ofer Neiman . Using petal-decompositions to build a low stretch spanning tree . In Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages 395\u2013 406 . ACM, 2012. Ittai Abraham and Ofer Neiman. Using petal-decompositions to build a low stretch spanning tree. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 395\u2013406. ACM, 2012."},{"key":"e_1_3_2_1_2_1","volume-title":"Parallel approximate undirected shortest paths via low hop emulators. arXiv preprint arXiv:1911.01956","author":"Andoni Alexandr","year":"2019","unstructured":"Alexandr Andoni , Clifford Stein , and Peilin Zhong . Parallel approximate undirected shortest paths via low hop emulators. arXiv preprint arXiv:1911.01956 , 2019 . Alexandr Andoni, Clifford Stein, and Peilin Zhong. Parallel approximate undirected shortest paths via low hop emulators. arXiv preprint arXiv:1911.01956, 2019."},{"key":"e_1_3_2_1_3_1","volume-title":"A combinatorial o(m 3\/2)-time algorithm for the min-cost flow problem. arXiv preprint arXiv:1312.3905","author":"Becker Ruben","year":"2013","unstructured":"Ruben Becker and Andreas Karrenbauer . A combinatorial o(m 3\/2)-time algorithm for the min-cost flow problem. arXiv preprint arXiv:1312.3905 , 2013 . Ruben Becker and Andreas Karrenbauer. A combinatorial o(m 3\/2)-time algorithm for the min-cost flow problem. arXiv preprint arXiv:1312.3905, 2013."},{"key":"e_1_3_2_1_4_1","volume-title":"Near-optimal approximate shortest paths and transshipment in distributed and streaming models. arXiv preprint arXiv:1607.05127","author":"Becker Ruben","year":"2016","unstructured":"Ruben Becker , Andreas Karrenbauer , Sebastian Krinninger , and Christoph Lenzen . Near-optimal approximate shortest paths and transshipment in distributed and streaming models. arXiv preprint arXiv:1607.05127 , 2016 . Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-optimal approximate shortest paths and transshipment in distributed and streaming models. arXiv preprint arXiv:1607.05127, 2016."},{"key":"e_1_3_2_1_5_1","first-page":"282","volume-title":"Proceedings of the forty-third annual ACM symposium on Theory of computing","author":"Christiano Paul","unstructured":"Paul Christiano , Jonathan A Kelner , Aleksander Madry , Daniel A Spielman , and Shang-Hua Teng . 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 , pages 273\u2013 282 . ACM, 2011. Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and Shang-Hua Teng. 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, pages 273\u2013282. ACM, 2011."},{"key":"e_1_3_2_1_6_1","first-page":"771","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Cohen Michael B","unstructured":"Michael B Cohen , Aleksander Madry , Piotr Sankowski , and Adrian Vladu . Negative-weight shortest paths and unit capacity minimum cost flow in o (m 10\/7 log w) time* . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 752\u2013 771 . SIAM, 2017. Michael B Cohen, Aleksander Madry, Piotr Sankowski, and Adrian Vladu. Negative-weight shortest paths and unit capacity minimum cost flow in o (m 10\/7 log w) time*. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 752\u2013771. SIAM, 2017."},{"key":"e_1_3_2_1_7_1","volume-title":"Polylog-time and near-linear work approximation scheme for undirected shortest paths. Journal of the ACM (JACM), 47(1):132\u2013166","author":"Cohen Edith","year":"2000","unstructured":"Edith Cohen . Polylog-time and near-linear work approximation scheme for undirected shortest paths. Journal of the ACM (JACM), 47(1):132\u2013166 , 2000 . Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. Journal of the ACM (JACM), 47(1):132\u2013166, 2000."},{"key":"e_1_3_2_1_8_1","first-page":"460","volume-title":"Proceedings of the fortieth annual ACM symposium on Theory of computing","author":"Daitch Samuel I","unstructured":"Samuel I Daitch and Daniel A Spielman . Faster approximate lossy generalized flow via interior point algorithms . In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 451\u2013 460 . ACM, 2008. Samuel I Daitch and Daniel A Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 451\u2013460. ACM, 2008."},{"key":"e_1_3_2_1_9_1","volume-title":"Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG), 15(1):4","author":"Elkin Michael","year":"2018","unstructured":"Michael Elkin and Ofer Neiman . Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG), 15(1):4 , 2018 . Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG), 15(1):4, 2018."},{"key":"e_1_3_2_1_10_1","first-page":"470","volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing","author":"Fineman Jeremy T","unstructured":"Jeremy T Fineman . Nearly work-efficient parallel algorithm for digraph reachability . In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 457\u2013 470 . ACM, 2018. Jeremy T Fineman. Nearly work-efficient parallel algorithm for digraph reachability. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 457\u2013470. ACM, 2018."},{"key":"e_1_3_2_1_11_1","first-page":"697","volume-title":"2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Forster Sebastian","unstructured":"Sebastian Forster and Danupon Nanongkai . A faster distributed single-source shortest paths algorithm . In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages 686\u2013 697 . IEEE, 2018. Sebastian Forster and Danupon Nanongkai. A faster distributed single-source shortest paths algorithm. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 686\u2013697. IEEE, 2018."},{"key":"e_1_3_2_1_12_1","volume-title":"American Mathematical Soc.","author":"Har-Peled Sariel","year":"2011","unstructured":"Sariel Har-Peled . Geometric approximation algorithms. Number 173 . American Mathematical Soc. , 2011 . Sariel Har-Peled. Geometric approximation algorithms. Number 173. American Mathematical Soc., 2011."},{"issue":"189","key":"e_1_3_2_1_13_1","first-page":"1","article-title":"Extensions of lipschitz mappings into a hilbert space","volume":"26","author":"Johnson William B","year":"1984","unstructured":"William B Johnson and Joram Lindenstrauss . Extensions of lipschitz mappings into a hilbert space . Contemporary mathematics , 26 ( 189-206 ): 1 , 1984 . William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984.","journal-title":"Contemporary mathematics"},{"key":"e_1_3_2_1_14_1","first-page":"226","volume-title":"Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms","author":"Kelner Jonathan A","unstructured":"Jonathan A Kelner , Yin Tat Lee , Lorenzo Orecchia , and Aaron Sidford . An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations . In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 217\u2013 226 . SIAM, 2014. Jonathan A Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 217\u2013226. SIAM, 2014."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/110845914"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/110845914"},{"key":"e_1_3_2_1_17_1","volume-title":"Preconditioning for the geometric transportation problem. arXiv preprint arXiv:1902.08384","author":"Khesin Andrey Boris","year":"2019","unstructured":"Andrey Boris Khesin , Aleksandar Nikolov , and Dmitry Paramonov . Preconditioning for the geometric transportation problem. arXiv preprint arXiv:1902.08384 , 2019 . Andrey Boris Khesin, Aleksandar Nikolov, and Dmitry Paramonov. Preconditioning for the geometric transportation problem. arXiv preprint arXiv:1902.08384, 2019."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129785"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0888"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/sfcs.1994.365733"},{"key":"e_1_3_2_1_21_1","first-page":"433","volume-title":"2014 IEEE 55th Annual Symposium on Foundations of Computer Science","author":"Lee Yin Tat","unstructured":"Yin Tat Lee and Aaron Sidford . Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow . In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science , pages 424\u2013 433 . IEEE, 2014. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 424\u2013433. IEEE, 2014."},{"key":"e_1_3_2_1_22_1","first-page":"254","volume-title":"FOCS","author":"Madry Aleksander","unstructured":"Aleksander Madry . Fast approximation algorithms for cut-based problems in undirected graphs . In FOCS , pages 245\u2013 254 . IEEE Computer Society, 2010. Aleksander Madry. Fast approximation algorithms for cut-based problems in undirected graphs. In FOCS, pages 245\u2013254. IEEE Computer Society, 2010."},{"key":"e_1_3_2_1_23_1","first-page":"262","volume-title":"2013 IEEE 54th Annual Symposium on Foundations of Computer Science","author":"Madry Aleksander","unstructured":"Aleksander Madry . Navigating central path with electrical flows: From flows to matchings, and back . In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science , pages 253\u2013 262 . IEEE, 2013. Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 253\u2013262. IEEE, 2013."},{"key":"e_1_3_2_1_24_1","volume-title":"Improved parallel algorithms for spanners and hopsets. arXiv preprint arXiv:1309.3545","author":"Miller Gary L","year":"2013","unstructured":"Gary L Miller , Richard Peng , Adrian Vladu , and Shen Chen Xu . Improved parallel algorithms for spanners and hopsets. arXiv preprint arXiv:1309.3545 , 2013 . Gary L Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. Improved parallel algorithms for spanners and hopsets. arXiv preprint arXiv:1309.3545, 2013."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0552-5"},{"key":"e_1_3_2_1_26_1","first-page":"1867","volume-title":"Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms","author":"Peng Richard","unstructured":"Richard Peng . Approximate undirected maximum flows in o (m polylog (n)) time . In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms , pages 1862\u2013 1867 . SIAM, 2016. Richard Peng. Approximate undirected maximum flows in o (m polylog (n)) time. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1862\u20131867. SIAM, 2016."},{"key":"e_1_3_2_1_27_1","first-page":"342","volume-title":"Proceedings of the forty-sixth annual ACM symposium on Theory of computing","author":"Peng Richard","unstructured":"Richard Peng and Daniel A Spielman . An efficient parallel solver for sdd linear systems . In Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages 333\u2013 342 . ACM, 2014. Richard Peng and Daniel A Spielman. An efficient parallel solver for sdd linear systems. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 333\u2013342. ACM, 2014."},{"key":"e_1_3_2_1_28_1","first-page":"264","volume-title":"Proceedings of the fortieth annual ACM symposium on Theory of computing","author":"R\u00e4cke Harald","unstructured":"Harald R\u00e4cke . Optimal hierarchical decompositions for congestion minimization in networks . In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 255\u2013 264 . ACM, 2008. Harald R\u00e4cke. Optimal hierarchical decompositions for congestion minimization in networks. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 255\u2013264. ACM, 2008."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2794549.3114257"},{"key":"e_1_3_2_1_30_1","first-page":"238","volume-title":"Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms","author":"R\u00e4cke Harald","unstructured":"Harald R\u00e4cke , Chintan Shah , and Hanjo T\u00e4ubig . Computing cut-based hierarchical decompositions in almost linear time . In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 227\u2013 238 . Society for Industrial and Applied Mathematics, 2014. Harald R\u00e4cke, Chintan Shah, and Hanjo T\u00e4ubig. Computing cut-based hierarchical decompositions in almost linear time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 227\u2013238. Society for Industrial and Applied Mathematics, 2014."},{"key":"e_1_3_2_1_31_1","first-page":"269","volume-title":"2013 IEEE 54th Annual Symposium on Foundations of Computer Science","author":"Sherman Jonah","unstructured":"Jonah Sherman . Nearly maximum flows in nearly linear time . In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science , pages 263\u2013 269 . IEEE, 2013. Jonah Sherman. Nearly maximum flows in nearly linear time. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 263\u2013269. IEEE, 2013."},{"key":"e_1_3_2_1_32_1","first-page":"460","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing","author":"Sherman Jonah","unstructured":"Jonah Sherman . Area-convexity, l\u221e regularization , and undirected multicommodity flow . In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 452\u2013 460 . ACM, 2017. Jonah Sherman. Area-convexity, l\u221e regularization, and undirected multicommodity flow. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 452\u2013460. ACM, 2017."},{"key":"e_1_3_2_1_33_1","first-page":"780","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Sherman Jonah","unstructured":"Jonah Sherman . Generalized preconditioning and undirected minimum-cost flow . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 772\u2013 780 . SIAM, 2017. Jonah Sherman. Generalized preconditioning and undirected minimum-cost flow. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 772\u2013780. SIAM, 2017."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/265937"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3384268","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384268","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.3384268"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":35,"alternative-id":["10.1145\/3357713.3384268","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384268","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"}}]}}