{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T04:16:46Z","timestamp":1777954606640,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,16]]},"DOI":"10.1145\/3694906.3743329","type":"proceedings-article","created":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:19:56Z","timestamp":1752682796000},"page":"210-224","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A New Algorithm for Online Scheduling of Rigid Task Graphs with Near-Optimal Competitive Ratio"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9739-7440","authenticated-orcid":false,"given":"Lucas","family":"Perotin","sequence":"first","affiliation":[{"name":"Vanderbilt University, Nashville, TN, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4379-4467","authenticated-orcid":false,"given":"Hongyang","family":"Sun","sequence":"additional","affiliation":[{"name":"University of Kansas, Lawrence, KS, United States"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-6785-2112","authenticated-orcid":false,"given":"Padma","family":"Raghavan","sequence":"additional","affiliation":[{"name":"Vanderbilt University, Nashville, TN, United States"}]}],"member":"320","published-online":{"date-parts":[[2025,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.024"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212033"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209064"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Krishna P. Belkhale Prithviraj Banerjee and W. Springfield Av. 1991. A Scheduling Algorithm for Parallelizable Dependent Tasks. In IPPS. 500--506.","DOI":"10.1109\/IPPS.1991.153827"},{"key":"e_1_3_2_1_5_1","first-page":"1","article-title":"Online Scheduling of Moldable Task Graphs under Common Speedup Models","volume":"51","author":"Benoit Anne","year":"2022","unstructured":"Anne Benoit, Lucas Perotin, Yves Robert, and Hongyang Sun. 2022. Online Scheduling of Moldable Task Graphs under Common Speedup Models. In ICPP. 51:1--51:11.","journal-title":"ICPP."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00040-0"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.258"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209062"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00120-8"},{"key":"e_1_3_2_1_10_1","volume-title":"Woeginger","author":"Csirik J\u00e1nos","year":"1998","unstructured":"J\u00e1nos Csirik and Gerhard J. Woeginger. 1998. On-line packing and covering problems. In Online Algorithms: The State of the Art, Amos Fiat and Gerhard J. Woeginger (Eds.). Springer, Chapter 7, 147--177."},{"key":"e_1_3_2_1_11_1","first-page":"1","article-title":"Approximation Algorithms for Scheduling with Resource and Precedence Constraints","volume":"25","author":"Demirci G\u00f6kalp","year":"2018","unstructured":"G\u00f6kalp Demirci, Henry Hoffmann, and David H. K. Kim. 2018. Approximation Algorithms for Scheduling with Resource and Precedence Constraints. In STACS. 25:1--25:14.","journal-title":"STACS."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"G\u00f6kalp Demirci Ivana Marincic and Henry Hoffmann. 2018. A divide and conquer algorithm for DAG scheduling under power constraints. In SC. Article 36 12 pages.","DOI":"10.1109\/SC.2018.00039"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009794729459"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90152-X"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204015"},{"key":"e_1_3_2_1_16_1","volume-title":"Computers and Intractability, a Guide to the Theory of NP-Completeness","author":"Garey M. R.","unstructured":"M. R. Garey and D. S.Johnson. 1979. Computers and Intractability, a Guide to the Theory of NP-Completeness. W.H. Freeman and Company."},{"key":"e_1_3_2_1_17_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_3_2_1_19_1","volume-title":"Hurink and Jacob Jan Paulus","author":"Johann","year":"2008","unstructured":"Johann L. Hurink and Jacob Jan Paulus. 2008. Online Algorithm for Parallel Job Scheduling and Strip Packing. In Approximation and Online Algorithms, Christos Kaklamanis and Martin Skutella (Eds.). Springer, 67--74."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Klaus Jansen. 2012. A (3\/2+ &epsis;) Approximation Algorithm for Scheduling Moldable and Non-moldable Parallel Tasks. In SPAA (Pittsburgh Pennsylvania USA). 224--235.","DOI":"10.1145\/2312005.2312048"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Klaus Jansen and Hu Zhang. 2005. Scheduling Malleable Tasks with Precedence Constraints. In SPAA. 86--95.","DOI":"10.1145\/1073970.1073983"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159899"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-006-8497-6"},{"key":"e_1_3_2_1_24_1","volume-title":"Woeginger","author":"Lep\u00e8re Renaud","year":"2001","unstructured":"Renaud Lep\u00e8re, Denis Trystram, and Gerhard J. Woeginger. 2001. Approximation Algorithms for Scheduling Malleable Tasks Under Precedence Constraints. In ESA. 146--157."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009817206440"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00123-6"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00241-1"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3630052"},{"key":"e_1_3_2_1_29_1","volume-title":"Yu","author":"Turek John","year":"1992","unstructured":"John Turek, Joel L. Wolf, and Philip S. Yu. 1992. Approximate Algorithms Scheduling Parallelizable Tasks. In SPAA (San Diego, California, USA)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9125-x"}],"event":{"name":"SPAA '25: 37th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Portland OR USA","acronym":"SPAA '25","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"]},"container-title":["Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3694906.3743329","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T19:18:53Z","timestamp":1777922333000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694906.3743329"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,16]]},"references-count":30,"alternative-id":["10.1145\/3694906.3743329","10.1145\/3694906"],"URL":"https:\/\/doi.org\/10.1145\/3694906.3743329","relation":{},"subject":[],"published":{"date-parts":[[2025,7,16]]},"assertion":[{"value":"2025-07-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}