{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T08:40:00Z","timestamp":1766220000479,"version":"3.48.0"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,9,8]]},"DOI":"10.1145\/3754598.3754676","type":"proceedings-article","created":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T08:34:32Z","timestamp":1766219672000},"page":"238-247","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Multiprocessor Scheduling with Memory Constraints: Fundamental Properties and Finding Optimal Solutions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-6667-802X","authenticated-orcid":false,"given":"P\u00e1l Andr\u00e1s","family":"Papp","sequence":"first","affiliation":[{"name":"Computing Systems Lab, Huawei Zurich Research Center, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-2152-022X","authenticated-orcid":false,"given":"Toni","family":"B\u00f6hnlein","sequence":"additional","affiliation":[{"name":"Computing Systems Lab, Huawei Zurich Research Center, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8842-3689","authenticated-orcid":false,"given":"Albert-Jan N.","family":"Yzelman","sequence":"additional","affiliation":[{"name":"Computing Systems Lab, Huawei Zurich Research Center, Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2025,12,20]]},"reference":[{"key":"e_1_3_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198788348.001.0001"},{"key":"e_1_3_3_1_3_2","first-page":"1820","volume-title":"Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security","author":"Blocki Jeremiah","year":"2018","unstructured":"Jeremiah Blocki, Ling Ren, and Samson Zhou. 2018. Bandwidth-hard functions: Reductions and lower bounds. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 1820\u20131836."},{"key":"e_1_3_3_1_4_2","doi-asserted-by":"crossref","unstructured":"Robert\u00a0D Blumofe and Charles\u00a0E Leiserson. 1999. Scheduling multithreaded computations by work stealing. Journal of the ACM (JACM) 46 5 (1999) 720\u2013748.","DOI":"10.1145\/324133.324234"},{"key":"e_1_3_3_1_5_2","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/978-3-031-91736-3_7","volume-title":"International Colloquium on Structural Information and Communication Complexity (SIROCCO)","author":"B\u00f6hnlein Toni","year":"2025","unstructured":"Toni B\u00f6hnlein, P\u00e1l\u00a0Andr\u00e1s Papp, and Albert-Jan\u00a0N. Yzelman. 2025. Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-Offs. In International Colloquium on Structural Information and Communication Complexity (SIROCCO). Springer, 109\u2013126."},{"key":"e_1_3_3_1_6_2","first-page":"161","volume-title":"Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Carpenter Timothy","year":"2016","unstructured":"Timothy Carpenter, Fabrice Rastello, P Sadayappan, and Anastasios Sidiropoulos. 2016. Brief announcement: Approximating the I\/O complexity of one-shot red-blue pebbling. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 161\u2013163."},{"key":"e_1_3_3_1_7_2","first-page":"657","volume-title":"Proceedings of the 25th annual ACM-SIAM symposium on Discrete algorithms (SODA)","author":"Chen Lin","year":"2014","unstructured":"Lin Chen, Klaus Jansen, and Guochuan Zhang. 2014. On the optimality of approximation schemes for the classical scheduling problem. In Proceedings of the 25th annual ACM-SIAM symposium on Discrete algorithms (SODA). SIAM, 657\u2013668."},{"key":"e_1_3_3_1_8_2","doi-asserted-by":"crossref","unstructured":"Edward\u00a0G Coffman and Ronald\u00a0L Graham. 1972. Optimal scheduling for two-processor systems. Acta informatica 1 3 (1972) 200\u2013213.","DOI":"10.1007\/BF00288685"},{"key":"e_1_3_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/155332.155333"},{"key":"e_1_3_3_1_10_2","first-page":"822","volume-title":"61st Annual Symposium on Foundations of Computer Science (FOCS)","author":"Davies Sami","year":"2020","unstructured":"Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, and Yihao Zhang. 2020. Scheduling with communication delays via LP hierarchies and clustering. In 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 822\u2013833."},{"key":"e_1_3_3_1_11_2","first-page":"2958","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Davies Sami","year":"2021","unstructured":"Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, and Yihao Zhang. 2021. Scheduling with communication delays via LP hierarchies and clustering II: weighted completion times on related machines. In ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2958\u20132977."},{"key":"e_1_3_3_1_12_2","first-page":"195","volume-title":"Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Demaine Erik\u00a0D","year":"2018","unstructured":"Erik\u00a0D Demaine and Quanquan\u00a0C Liu. 2018. Red-blue pebble game: Complexity of computing the trade-off between cache size and memory transfers. In Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 195\u2013204."},{"key":"e_1_3_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612694"},{"key":"e_1_3_3_1_14_2","doi-asserted-by":"crossref","unstructured":"Lionel Eyraud-Dubois Loris Marchal Oliver Sinnen and Fr\u00e9d\u00e9ric Vivien. 2015. Parallel scheduling of task trees with limited memory. ACM Transactions on Parallel Computing (TOPC) 2 2 (2015) 1\u201337.","DOI":"10.1145\/2779052"},{"key":"e_1_3_3_1_15_2","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)","author":"Garg Shashwat","year":"2018","unstructured":"Shashwat Garg. 2018. Quasi-PTAS for Scheduling with Precedences using LP Hierarchies. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_3_1_16_2","unstructured":"Dongdong Ge Qi Huangfu Zizhuo Wang Jian Wu and Yinyu Ye. 2023. Cardinal Optimizer (COPT) user guide. https:\/\/guide.coap.online\/copt\/en-doc."},{"key":"e_1_3_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-09993-9_8"},{"key":"e_1_3_3_1_18_2","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1109\/ETFA.1995.496773","volume-title":"Proceedings 1995 INRIA\/IEEE Symposium on Emerging Technologies and Factory Automation (ETFA)","volume":"1","author":"Hanen Claire","year":"1995","unstructured":"Claire Hanen and Alix Munier. 1995. An approximation algorithm for scheduling dependent tasks on m processors with small communication delays. In Proceedings 1995 INRIA\/IEEE Symposium on Emerging Technologies and Factory Automation (ETFA), Vol.\u00a01. IEEE, 167\u2013189."},{"key":"e_1_3_3_1_19_2","doi-asserted-by":"crossref","unstructured":"Jonathan\u00a0MD Hill Bill McColl Dan\u00a0C Stefanescu Mark\u00a0W Goudreau Kevin Lang Satish\u00a0B Rao Torsten Suel Thanasis Tsantilas and Rob\u00a0H Bisseling. 1998. BSPlib: The BSP programming library. Parallel Comput. 24 14 (1998) 1947\u20131980.","DOI":"10.1016\/S0167-8191(98)00093-3"},{"key":"e_1_3_3_1_20_2","first-page":"326","volume-title":"Proceedings of the 13th ACM Symposium on Theory of Computing (STOC)","author":"Hong Jia-Wei","year":"1981","unstructured":"Jia-Wei Hong and Hsiang-Tsung Kung. 1981. I\/O complexity: The red-blue pebble game. In Proceedings of the 13th ACM Symposium on Theory of Computing (STOC). 326\u2013333."},{"key":"e_1_3_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400210"},{"key":"e_1_3_3_1_22_2","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1109\/IPDPSW55747.2022.00129","volume-title":"2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)","author":"Jenneskens Engelina\u00a0L","year":"2022","unstructured":"Engelina\u00a0L Jenneskens and Rob\u00a0H Bisseling. 2022. Exact k-way sparse matrix partitioning. In 2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 754\u2013763."},{"key":"e_1_3_3_1_23_2","doi-asserted-by":"crossref","unstructured":"Enver Kayaaslan Thomas Lambert Loris Marchal and Bora U\u00e7ar. 2018. Scheduling series-parallel task graphs to minimize peak memory. Theoretical Computer Science 707 (2018) 1\u201323.","DOI":"10.1016\/j.tcs.2017.09.037"},{"key":"e_1_3_3_1_24_2","first-page":"2770","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Kulkarni Janardhan","year":"2020","unstructured":"Janardhan Kulkarni, Shi Li, Jakub Tarnawski, and Minwei Ye. 2020. Hierarchy-based algorithms for minimizing makespan under precedence and communication constraints. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2770\u20132789."},{"key":"e_1_3_3_1_25_2","first-page":"328","volume-title":"Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Kwasniewski Grzegorz","year":"2021","unstructured":"Grzegorz Kwasniewski, Tal Ben-Nun, Lukas Gianinazzi, Alexandru Calotoiu, Timo Schneider, Alexandros\u00a0Nikolaos Ziogas, Maciej Besta, and Torsten Hoefler. 2021. Pebbles, graphs, and a pinch of combinatorics: Towards tight I\/O lower bounds for statically analyzable programs. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 328\u2013339."},{"key":"e_1_3_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356181"},{"key":"e_1_3_3_1_27_2","first-page":"343","volume-title":"Annals of discrete mathematics","author":"Lenstra Jan\u00a0Karel","year":"1977","unstructured":"Jan\u00a0Karel Lenstra, AHG\u00a0Rinnooy Kan, and Peter Brucker. 1977. Complexity of machine scheduling problems. In Annals of discrete mathematics. Vol.\u00a01. Elsevier, 343\u2013362."},{"key":"e_1_3_3_1_28_2","first-page":"154","volume-title":"Annual Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Lepere Renaud","year":"2002","unstructured":"Renaud Lepere and Christophe Rapine. 2002. An Asymptotic \\(\\mathcal {\\lbrace }O\\rbrace (ln \\rho \/ ln ln \\rho)\\)-Approximation Algorithm for the Scheduling Problem with Duplication on Large Communication Delay Graphs. In Annual Symposium on Theoretical Aspects of Computer Science (STACS). Springer, 154\u2013165."},{"key":"e_1_3_3_1_29_2","first-page":"168","volume-title":"Proceedings of the 48th annual ACM Symposium on Theory of Computing (STOC)","author":"Levey Elaine","year":"2016","unstructured":"Elaine Levey and Thomas Rothvoss. 2016. A (1+ epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. In Proceedings of the 48th annual ACM Symposium on Theory of Computing (STOC). 168\u2013177."},{"key":"e_1_3_3_1_30_2","first-page":"2991","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Li Shi","year":"2021","unstructured":"Shi Li. 2021. Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2991\u20133010."},{"key":"e_1_3_3_1_31_2","volume-title":"39th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Liu Quanquan\u00a0C","year":"2022","unstructured":"Quanquan\u00a0C Liu, Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua\u00a0R Wang. 2022. Scheduling with Communication Delay in Near-Linear Time. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_3_1_32_2","first-page":"834","volume-title":"61st Annual Symposium on Foundations of Computer Science (FOCS)","author":"Maiti Biswaroop","year":"2020","unstructured":"Biswaroop Maiti, Rajmohan Rajaraman, David Stalfa, Zoya Svitkina, and Aravindan Vijayaraghavan. 2020. Scheduling precedence-constrained jobs on related machines with communication delay. In 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 834\u2013845."},{"key":"e_1_3_3_1_33_2","first-page":"6","volume-title":"Mathematics, Models and Architectures","author":"McColl Bill","year":"2021","unstructured":"Bill McColl. 2021. Mathematics, Models and Architectures. Cambridge University Press, 6\u201353."},{"key":"e_1_3_3_1_34_2","doi-asserted-by":"crossref","unstructured":"WF McColl and A Tiskin. 1999. Memory-efficient matrix computations in the BSP model. Algorithmica 24 3-4 (1999) 287\u2013297.","DOI":"10.1007\/PL00008264"},{"key":"e_1_3_3_1_35_2","first-page":"155","volume-title":"IEEE International Parallel and Distributed Processing Symposium (IPDPS)","author":"\u00d6zkaya M.\u00a0Yusuf","year":"2019","unstructured":"M.\u00a0Yusuf \u00d6zkaya, Anne Benoit, Bora U\u00e7ar, Julien Herrmann, and \u00dcmit\u00a0V. \u00c7ataly\u00fcrek. 2019. A Scalable Clustering-Based Task Scheduler for Homogeneous Processors Using DAG Partitioning. In IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 155\u2013165."},{"key":"e_1_3_3_1_36_2","first-page":"510","volume-title":"Proceedings of the 20th annual ACM symposium on Theory of computing (STOC)","author":"Papadimitriou Christos","year":"1988","unstructured":"Christos Papadimitriou and Mihalis Yannakakis. 1988. Towards an architecture-independent analysis of parallel algorithms. In Proceedings of the 20th annual ACM symposium on Theory of computing (STOC). 510\u2013513."},{"key":"e_1_3_3_1_37_2","first-page":"463","volume-title":"Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Papp P\u00e1l\u00a0Andr\u00e1s","year":"2024","unstructured":"P\u00e1l\u00a0Andr\u00e1s Papp, Georg Anegg, Aikaterini Karanasiou, and Albert-Jan\u00a0N Yzelman. 2024. Efficient Multi-Processor Scheduling in Increasingly Realistic Models. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 463\u2013474."},{"key":"e_1_3_3_1_38_2","first-page":"238","volume-title":"International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)","author":"Papp P\u00e1l\u00a0Andr\u00e1s","year":"2025","unstructured":"P\u00e1l\u00a0Andr\u00e1s Papp, Georg Anegg, and Albert-Jan\u00a0N Yzelman. 2025. DAG Scheduling in the BSP Model. In International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). Springer, 238\u2013253."},{"key":"e_1_3_3_1_39_2","unstructured":"P\u00e1l\u00a0Andr\u00e1s Papp Toni B\u00f6hnlein and A.\u00a0N. Yzelman. 2025. Multiprocessor Scheduling with Memory Constraints: Fundamental Properties and Finding Optimal Solutions (full version). arXiv preprint arXiv:https:\/\/arXiv.org\/abs\/2507.17411 (2025)."},{"key":"e_1_3_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400278"},{"key":"e_1_3_3_1_41_2","doi-asserted-by":"crossref","unstructured":"Ravi Sethi. 1976. Scheduling graphs on two processors. SIAM J. Comput. 5 1 (1976) 73\u201382.","DOI":"10.1137\/0205005"},{"key":"e_1_3_3_1_42_2","first-page":"745","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC)","author":"Svensson Ola","year":"2010","unstructured":"Ola Svensson. 2010. Conditional hardness of precedence constrained scheduling on identical machines. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC). 745\u2013754."},{"key":"e_1_3_3_1_43_2","doi-asserted-by":"crossref","unstructured":"Leslie\u00a0G Valiant. 1990. A bridging model for parallel computation. Commun. ACM 33 8 (1990) 103\u2013111.","DOI":"10.1145\/79173.79181"},{"key":"e_1_3_3_1_44_2","first-page":"13","volume-title":"European Symposium on Algorithms (ESA)","author":"Valiant Leslie\u00a0G","year":"2008","unstructured":"Leslie\u00a0G Valiant. 2008. A bridging model for multi-core computing. In European Symposium on Algorithms (ESA). Springer, 13\u201328."},{"key":"e_1_3_3_1_45_2","doi-asserted-by":"crossref","unstructured":"Leslie\u00a0G Valiant. 2011. A bridging model for multi-core computing. J. Comput. System Sci. 77 1 (2011) 154\u2013166.","DOI":"10.1016\/j.jcss.2010.06.012"},{"key":"e_1_3_3_1_46_2","doi-asserted-by":"crossref","unstructured":"Bart Veltman BJ Lageweg and Jan\u00a0Karel Lenstra. 1990. Multiprocessor scheduling with communication delays. Parallel computing 16 2-3 (1990) 173\u2013182.","DOI":"10.1016\/0167-8191(90)90056-F"},{"key":"e_1_3_3_1_47_2","doi-asserted-by":"crossref","unstructured":"AN Yzelman Rob\u00a0H Bisseling Dirk Roose and Karl Meerbergen. 2014. MulticoreBSP for C: a high-performance library for shared-memory parallel programming. International Journal of Parallel Programming 42 4 (2014) 619\u2013642.","DOI":"10.1007\/s10766-013-0262-9"}],"event":{"name":"ICPP '25: 54th International Conference on Parallel Processing","location":"San Diego CA USA","acronym":"ICPP '25"},"container-title":["Proceedings of the 54th International Conference on Parallel Processing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3754598.3754676","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T08:38:19Z","timestamp":1766219899000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3754598.3754676"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,8]]},"references-count":46,"alternative-id":["10.1145\/3754598.3754676","10.1145\/3754598"],"URL":"https:\/\/doi.org\/10.1145\/3754598.3754676","relation":{},"subject":[],"published":{"date-parts":[[2025,9,8]]},"assertion":[{"value":"2025-12-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}