{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T04:16:57Z","timestamp":1777954617092,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":63,"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.3743340","type":"proceedings-article","created":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:19:56Z","timestamp":1752682796000},"page":"46-61","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Hardness of Resource Scheduling"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2416-6422","authenticated-orcid":false,"given":"Rathish","family":"Das","sequence":"first","affiliation":[{"name":"University of Houston, Houston, Texas, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2000-8080","authenticated-orcid":false,"given":"Hao","family":"Sun","sequence":"additional","affiliation":[{"name":"University of Houston, Houston, Texas, 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.1145\/3350755.3400231"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.180"},{"key":"e_1_3_2_1_3_1","first-page":"205","volume-title":"Proc. 34th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Agrawal Kunal","year":"2022","unstructured":"Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato. Online parallel paging with optimal makespan. In Kunal Agrawal and I-Ting Angelina Lee, editors, Proc. 34th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA), Philadelphia, PA, USA, July 11-14, 2022, pages 205--216."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2018.09.014"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148109.1148139"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00272-4"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212033"},{"key":"e_1_3_2_1_8_1","first-page":"61801","article-title":"An approximate algorithm for the partitionable independent task scheduling problem","volume":"51","author":"Banerjee KPBP","year":"1990","unstructured":"KPBP Banerjee. An approximate algorithm for the partitionable independent task scheduling problem. Urbana, 51:61801, 1990.","journal-title":"Urbana"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/372202.372275"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/341800.341803"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/356989.357000"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492464"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/209937.209958"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167196"},{"key":"e_1_3_2_1_15_1","volume-title":"Scheduling multithreaded computations by work stealing. Journal of the ACM (JACM), 46(5):720--748","author":"Blumofe Robert D","year":"1999","unstructured":"Robert D Blumofe and Charles E Leiserson. Scheduling multithreaded computations by work stealing. Journal of the ACM (JACM), 46(5):720--748, 1999."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(98)00204-5"},{"key":"e_1_3_2_1_17_1","series-title":"SIAM journal on computing, 33(4):837--851","volume-title":"On multidimensional packing problems","author":"Chekuri Chandra","year":"2004","unstructured":"Chandra Chekuri and Sanjeev Khanna. On multidimensional packing problems. SIAM journal on computing, 33(4):837--851, 2004."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.258"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2016.12.001"},{"key":"e_1_3_2_1_20_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H","year":"2022","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00120-8"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400233"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323209"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538570"},{"key":"e_1_3_2_1_25_1","volume-title":"35th Symposium on Theoretical Aspects of Computer Science (STACS 2018","author":"Demirci G\u00f6kalp","year":"2018","unstructured":"G\u00f6kalp Demirci, Henry Hoffmann, and David HK Kim. Approximation algorithms for scheduling with resource and precedence constraints. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018."},{"key":"e_1_3_2_1_26_1","unstructured":"Huseyin Gokalp Demirci. Approximation algorithms for capacitated k-median and scheduling with resource and precedence constraints."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2013.102"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402042"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/646687.702952"},{"key":"e_1_3_2_1_30_1","volume-title":"A note on on-line scheduling with precedence constraints on identical machines. Information processing letters, 76(4-6):149--153","author":"Epstein Leah","year":"2000","unstructured":"Leah Epstein. A note on on-line scheduling with precedence constraints on identical machines. Information processing letters, 76(4-6):149--153, 2000."},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing","author":"Feldmann Anja","year":"1993","unstructured":"Anja Feldmann, Ming-Yang Kao, Jir\u00ed Sgall, and Shang-Hua Teng. Optimal online scheduling of parallel jobs with dependencies. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 642--651. ACM, 1993."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277725"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204015"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03784-9_27"},{"key":"e_1_3_2_1_35_1","volume-title":"Bounds for certain multiprocessing anomalies. Bell system technical journal, 45(9):1563--1581","author":"Graham Ronald L","year":"1966","unstructured":"Ronald L Graham. Bounds for certain multiprocessing anomalies. Bell system technical journal, 45(9):1563--1581, 1966."},{"key":"e_1_3_2_1_36_1","volume-title":"Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Mathematics of operations research, 22(3):513--544","author":"Hall Leslie A","year":"1997","unstructured":"Leslie A Hall, Andreas S Schulz, David B Shmoys, and Joel Wein. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Mathematics of operations research, 22(3):513--544, 1997."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72870-2_34"},{"key":"e_1_3_2_1_38_1","volume-title":"Approximation and Online Algorithms: 5th International Workshop, WAOA 2007","author":"Hurink Johann L","year":"2007","unstructured":"Johann L Hurink and Jacob Jan Paulus. Online algorithm for parallel job scheduling and strip packing. In Approximation and Online Algorithms: 5th International Workshop, WAOA 2007, Eilat, Israel, October 11-12, 2007. Revised Papers 5, pages 67--74. Springer, 2008."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.39"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0085-8"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1078-6"},{"key":"e_1_3_2_1_42_1","volume-title":"Approximation schemes for machine scheduling with resource (in-) dependent processing times. ACM Transactions on Algorithms (TALG), 15(3):1--28","author":"Jansen Klaus","year":"2019","unstructured":"Klaus Jansen, Marten Maack, and Malin Rau. Approximation schemes for machine scheduling with resource (in-) dependent processing times. ACM Transactions on Algorithms (TALG), 15(3):1--28, 2019."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159899"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979223842X"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2015.119"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0483(00)00046-3"},{"key":"e_1_3_2_1_47_1","series-title":"Proceedings of Machine Learning Research","first-page":"18563","volume-title":"International Conference on Machine Learning, ICML","author":"Lassota Alexandra Anna","year":"2023","unstructured":"Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schl\u00f6ter. Minimalistic predictions to schedule jobs with online precedence constraints. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 18563--18583. PMLR, 2023."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.1.22"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00264-3"},{"key":"e_1_3_2_1_50_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"Ludwig Walter","year":"1994","unstructured":"Walter Ludwig and Prasoon Tiwari. Scheduling malleable and nonmalleable parallel tasks. In ACM-SIAM Symposium on Discrete Algorithms, 1994."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.36"},{"key":"e_1_3_2_1_52_1","volume-title":"Stochastic online scheduling with precedence constraints","author":"Megow Nicole","year":"2009","unstructured":"Nicole Megow and Tjark Vredeveld. Stochastic online scheduling with precedence constraints. 2009."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/305619.305622"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9829-5"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3472456.3472487"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799358094"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90075-X"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133956.1133968"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806791"},{"key":"e_1_3_2_1_61_1","first-page":"1","volume-title":"Introduction to cloud computing. Cloud computing: Principles and paradigms","author":"Voorsluys William","year":"2011","unstructured":"William Voorsluys, James Broberg, and Rajkumar Buyya. Introduction to cloud computing. Cloud computing: Principles and paradigms, pages 1--41, 2011."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9125-x"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2011.940269"}],"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.3743340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T19:20:47Z","timestamp":1777922447000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694906.3743340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,16]]},"references-count":63,"alternative-id":["10.1145\/3694906.3743340","10.1145\/3694906"],"URL":"https:\/\/doi.org\/10.1145\/3694906.3743340","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"}}]}}