{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T16:40:06Z","timestamp":1755880806199,"version":"3.44.0"},"publisher-location":"New York, NY, USA","reference-count":90,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T00:00:00Z","timestamp":1718582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2103483, IIS-2227669, CCF-2238358, CCF-2339310"],"award-info":[{"award-number":["CCF-2103483, IIS-2227669, CCF-2238358, CCF-2339310"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"UCR Regents Faculty Development Award"},{"name":"Google Research Scholar Program"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,17]]},"DOI":"10.1145\/3626183.3659958","type":"proceedings-article","created":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T18:23:04Z","timestamp":1717525384000},"page":"219-232","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Parallel and (Nearly) Work-Efficient Dynamic Programming"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-8367-8399","authenticated-orcid":false,"given":"Xiangyun","family":"Ding","sequence":"first","affiliation":[{"name":"University of California, Riverside, Riverside, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4392-4022","authenticated-orcid":false,"given":"Yan","family":"Gu","sequence":"additional","affiliation":[{"name":"University of California, Riverside, Riverside, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3212-0934","authenticated-orcid":false,"given":"Yihan","family":"Sun","sequence":"additional","affiliation":[{"name":"University of California, Riverside, Riverside, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90124-U"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840359"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3354265.3354285"},{"volume-title":"IEEE Symposium on Foundations of Computer Science (FOCS). 497--512","author":"Alok Aggarwal","key":"e_1_3_2_1_4_1","unstructured":"Aggarwal Alok and Park James. [n.d.]. Notes on searching in multidimensional monotone arrays. In IEEE Symposium on Foundations of Computer Science (FOCS). 497--512."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/564870.564916"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219066"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840365"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002240011004"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/72935.72980"},{"key":"e_1_3_2_1_10_1","volume-title":"ADEPT: a domain independent sequence alignment strategy for gpu architectures. BMC bioinformatics","author":"Awan Muaaz G","year":"2020","unstructured":"Muaaz G Awan, Jack Deslippe, Aydin Buluc, Oguz Selvitopi, Steven Hofmeyr, Leonid Oliker, and Katherine Yelick. 2020. ADEPT: a domain independent sequence alignment strategy for gpu architectures. BMC bioinformatics, Vol. 21, 1 (2020), 1--29."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/HIPC.1997.634481"},{"key":"e_1_3_2_1_12_1","volume-title":"Massively parallel dynamic programming on trees. arXiv preprint arXiv:1809.03685","author":"Bateni MohammadHossein","year":"2018","unstructured":"MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Vahab Mirrokni. 2018. Massively parallel dynamic programming on trees. arXiv preprint arXiv:1809.03685 (2018)."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1954-09848-8"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400254"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400227"},{"key":"e_1_3_2_1_16_1","volume-title":"Blelloch and Yan Gu","author":"Guy","year":"2020","unstructured":"Guy E. Blelloch and Yan Gu. 2020. Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS)."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3402819"},{"key":"e_1_3_2_1_18_1","volume-title":"Parallel Shortest Paths Using Radius Stepping. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 443--454","author":"Blelloch Guy E.","year":"2016","unstructured":"Guy E. Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan. 2016. Parallel Shortest Paths Using Radius Stepping. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 443--454."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323205"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/279082.279099"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3558481.3591078"},{"key":"e_1_3_2_1_23_1","volume-title":"International Symposium on Algorithms. Springer, 318--327","author":"Lam Chan","year":"1990","unstructured":"Kwong-fai Chan and Tak-wah Lam. 1990. Finding least-weight subsequences with fewer processors. In International Symposium on Algorithms. Springer, 318--327."},{"key":"e_1_3_2_1_24_1","volume-title":"A fast parallel algorithm for finding the longest common sequence of multiple biosequences. BMC bioinformatics","author":"Chen Yixin","year":"2006","unstructured":"Yixin Chen, Andrew Wan, and Wei Liu. 2006. A fast parallel algorithm for finding the longest common sequence of multiple biosequences. BMC bioinformatics , Vol. 7 (2006), 1--12."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851167"},{"key":"e_1_3_2_1_26_1","volume-title":"Chowdhury and Vijaya Ramachandran","author":"Rezaul","year":"2006","unstructured":"Rezaul A. Chowdhury and Vijaya Ramachandran. 2006. Cache-oblivious dynamic programming. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 591--600."},{"volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM.","author":"Rezaul","key":"e_1_3_2_1_27_1","unstructured":"Rezaul A. Chowdhury and Vijaya Ramachandran. 2008. Cache-efficient dynamic programming algorithms for multicores. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9273-8"},{"key":"e_1_3_2_1_29_1","unstructured":"Artur Czumaj. 1992. Parallel algorithm for the matrix chain product problem. (1992)."},{"key":"e_1_3_2_1_30_1","unstructured":"Sashka Davis. 1998. Hu-Tucker alogorithm for building optimal alphabetic binary search trees. (1998)."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434393"},{"key":"e_1_3_2_1_32_1","volume-title":"Efficient Parallel Output-Sensitive Edit Distance. In European Symposium on Algorithms (ESA).","author":"Ding Xiangyun","year":"2023","unstructured":"Xiangyun Ding, Xiaojun Dong, Yan Gu, Yihan Sun, and Youzhe Liu. 2023. Efficient Parallel Output-Sensitive Edit Distance. In European Symposium on Algorithms (ESA)."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Xiangyun Ding Yan Gu and Yihan Sun. 2024 a. Parallel and (Nearly) Work-Efficient Dynamic Programming. arXiv preprint arXiv:2404.16314.","DOI":"10.1145\/3626183.3659958"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Xiangyun Ding Yan Gu and Yihan Sun. 2024 b. Source Code. https:\/\/github.com\/ucrparlay\/Parallel-Work-Efficient-Dynamic-Programming.","DOI":"10.1145\/3626183.3659958"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90031-9"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21965"},{"key":"e_1_3_2_1_37_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA). 513--522","author":"Eppstein David","year":"1990","unstructured":"David Eppstein, Zvi Galil, Raffaele Giancarlo, and Giuseppe F Italiano. 1990. Sparse dynamic programming. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 513--522."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146650"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146656"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90101-1"},{"key":"e_1_3_2_1_41_1","unstructured":"Zvi Galil and Kunsoo Park. 1989. A linear-time algorithm for concave one-dimensional dynamic programming. (1989)."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90135-3"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1053"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206045"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3558481.3591069"},{"key":"e_1_3_2_1_46_1","volume-title":"Analysis of Work-Stealing and Parallel Cache Complexity. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). SIAM, 46--60","author":"Gu Yan","year":"2022","unstructured":"Yan Gu, Zachary Napier, and Yihan Sun. 2022a. Analysis of Work-Stealing and Parallel Cache Complexity. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). SIAM, 46--60."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538581"},{"key":"e_1_3_2_1_48_1","volume-title":"Fast Dynamic Programming in Trees in the MPC Model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 443--453","author":"Gupta Chetan","year":"2023","unstructured":"Chetan Gupta, Rustam Latypov, Yannic Maus, Shreyas Pai, Simo S\"arkk\"a, Jan Studen\u1ef3 , Jukka Suomela, Jara Uitto, and Hossein Vahidi. 2023. Fast Dynamic Programming in Trees in the MPC Model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 443--453."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322044"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216043"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0121057"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.277784"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/359581.359603"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055460"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205002"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2983993"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3299109"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00296-4"},{"volume-title":"A simple linear time algorithm for concave one-dimensional dynamic programming","author":"Klawe Maria M.","key":"e_1_3_2_1_60_1","unstructured":"Maria M. Klawe. 1989. A simple linear time algorithm for concave one-dimensional dynamic programming. University of British Columbia Vancouver."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403009"},{"key":"e_1_3_2_1_62_1","volume-title":"Optimum binary search trees. Acta informatica","author":"Knuth Donald E.","year":"1971","unstructured":"Donald E. Knuth. 1971. Optimum binary search trees. Acta informatica , Vol. 1 (1971), 14--25."},{"volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth Donald E.","key":"e_1_3_2_1_63_1","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380111102"},{"key":"e_1_3_2_1_65_1","volume-title":"International Conference on Parallel Processing and Applied Mathematics. Springer, 176--185","author":"Krusche Peter","year":"2009","unstructured":"Peter Krusche and Alexander Tiskin. 2009. Parallel longest increasing subsequences in scalable time and memory. In International Conference on Parallel Processing and Applied Mathematics. Springer, 176--185."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810521"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792233245"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0067"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0934"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/165231.165259"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90136-8"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90016-R"},{"key":"e_1_3_2_1_73_1","volume-title":"A parallel dynamic programming algorithm for multi-reservoir system optimization. Advances in water resources","author":"Li Xiang","year":"2014","unstructured":"Xiang Li, Jiahua Wei, Tiejian Li, Guangqian Wang, and William W-G Yeh. 2014. A parallel dynamic programming algorithm for multi-reservoir system optimization. Advances in water resources , Vol. 67 (2014), 1--15."},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.298210"},{"key":"e_1_3_2_1_75_1","volume-title":"Sequence comparison with concave weighting functions. Bulletin of mathematical biology","author":"Miller Webb","year":"1988","unstructured":"Webb Miller and Eugene W Myers. 1988. Sequence comparison with concave weighting functions. Bulletin of mathematical biology , Vol. 50 (1988), 97--120."},{"key":"e_1_3_2_1_76_1","unstructured":"Gaspard Monge. 1781. M\u00e9moire sur la th\u00e9orie des d\u00e9blais et des remblais. Mem. Math. Phys. Acad. Royale Sci. ( 1781) 666--704."},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00320-9"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90147-8"},{"key":"e_1_3_2_1_79_1","volume-title":"Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Shen Zheqi","year":"2022","unstructured":"Zheqi Shen, Zijin Wan, Yan Gu, and Yihan Sun. 2022. Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087593"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688514"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2019.102598"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.107"},{"key":"e_1_3_2_1_84_1","volume-title":"Parallel Longest Common SubSequence Analysis In Chapel. In 2023 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, 1--6.","author":"Vahidi Soroush","year":"2023","unstructured":"Soroush Vahidi, Baruch Schieber, Zhihui Du, and David A Bader. 2023. Parallel Longest Common SubSequence Analysis In Chapel. In 2023 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, 1--6."},{"key":"e_1_3_2_1_85_1","unstructured":"Jan Van Leeuwen. 1976. On the Construction of Huffman Trees. In ICALP. 382--410."},{"key":"e_1_3_2_1_86_1","volume-title":"Computation of Matrix Chain Products on Parallel Machines. In International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 491--500","author":"Weiss Elad","year":"2019","unstructured":"Elad Weiss and Oded Schwartz. 2019. Computation of Matrix Chain Products on Parallel Machines. In International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 491--500."},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90032-6"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1007\/11424857_37"},{"key":"e_1_3_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804691"},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1137\/0603055"}],"event":{"name":"SPAA '24: 36th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Nantes France","acronym":"SPAA '24"},"container-title":["Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626183.3659958","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626183.3659958","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T16:23:03Z","timestamp":1755879783000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626183.3659958"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,17]]},"references-count":90,"alternative-id":["10.1145\/3626183.3659958","10.1145\/3626183"],"URL":"https:\/\/doi.org\/10.1145\/3626183.3659958","relation":{},"subject":[],"published":{"date-parts":[[2024,6,17]]},"assertion":[{"value":"2024-06-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}