{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T19:23:22Z","timestamp":1774121002343,"version":"3.50.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>\n            In this article, we study the problem of scheduling malleable tasks with precedence constraints. We are given\n            <jats:italic>m<\/jats:italic>\n            identical processors and\n            <jats:italic>n<\/jats:italic>\n            tasks. For each task the processing time is a function of the number of processors allotted to it. In addition, the tasks must be processed according to the precedence constraints. The goal is to minimize the makespan (maximum completion time) of the resulting schedule. The best previous approximation algorithm (that works in two phases) in Lep\u00e8re et al. [2002b] has a ratio 3 + \u221a5\u2248 5.236. We develop an improved approximation algorithm with a ratio at most 100\/43 + 100(\u221a4349 \u2212 7)\/2451 \u2248 4.730598. We also show that our resulting ratio is asymptotically tight.\n          <\/jats:p>","DOI":"10.1145\/1159892.1159899","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"416-434","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["An approximation algorithm for scheduling malleable tasks under general precedence constraints"],"prefix":"10.1145","volume":"2","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[{"name":"University of Kiel, Kiel, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hu","family":"Zhang","sequence":"additional","affiliation":[{"name":"McMaster University, Hamilton, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 5th European Conference on Parallel Computing (Euro-Par","volume":"1685","author":"Blayo E.","year":"1999","unstructured":"Blayo , E. , Debrue , L. , Mouni\u00e9 , G. , and Trystram , D . 1999. Dynamic load balancing for ocean circulation with adaptive meshing . In Proceedings of the 5th European Conference on Parallel Computing (Euro-Par 1999 ). Lecture Notes in Computer Science , Vol. 1685 . Springer-Verlag, New York, 303--312. Blayo, E., Debrue, L., Mouni\u00e9, G., and Trystram, D. 1999. Dynamic load balancing for ocean circulation with adaptive meshing. In Proceedings of the 5th European Conference on Parallel Computing (Euro-Par 1999). Lecture Notes in Computer Science, Vol. 1685. Springer-Verlag, New York, 303--312."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/240455.240477"},{"key":"e_1_2_1_3_1","unstructured":"Culler D. E. Singh J. P. and Gupta A. 1999. Parallel Computer Architecture: A Hardware\/Software Approach. Morgan Kaufmann San Francisco CA.   Culler D. E. Singh J. P. and Gupta A. 1999. Parallel Computer Architecture: A Hardware\/Software Approach. Morgan Kaufmann San Francisco CA."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402042"},{"key":"e_1_2_1_5_1","unstructured":"Dutot P.-F. Mouni\u00e9 G. and Trystram D. 2004. Scheduling parallel tasks---Approximation algorithms. In Handbook of Scheduling: Algorithms Models and Performance Analysis J. Y.-T. Leung Eds. CRC Press Boca Raton FL.  Dutot P.-F. Mouni\u00e9 G. and Trystram D. 2004. Scheduling parallel tasks---Approximation algorithms. In Handbook of Scheduling: Algorithms Models and Performance Analysis J. Y.-T. Leung Eds. CRC Press Boca Raton FL."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204015"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218016"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1078-6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0085-8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073983"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00031-4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.1.22"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00264-3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054102001308"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Ludwig W.","year":"1994","unstructured":"Ludwig , W. , and Tiwari , P . 1994. Scheduling malleable and nonmalleable parallel tasks . In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA 1994 ). ACM, New York, 167--176. Ludwig, W., and Tiwari, P. 1994. Scheduling malleable and nonmalleable parallel tasks. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA 1994). ACM, New York, 167--176."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/305619.305622"},{"key":"e_1_2_1_18_1","unstructured":"Mouni\u00e9 G. Rapine C. and Trystram D. 2002. A 3\/2-dual approximation algorithm for scheduling independent monotonic malleable tasks manuscript. http:\/\/www.id.imag.fl\/Laboratorie\/Membres\/Trystram_Denis\/publis_mallen.  Mouni\u00e9 G. Rapine C. and Trystram D. 2002. A 3\/2-dual approximation algorithm for scheduling independent monotonic malleable tasks manuscript. http:\/\/www.id.imag.fl\/Laboratorie\/Membres\/Trystram_Denis\/publis_mallen."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/113379.113399"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.4.909"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/140901.141909"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1159892.1159899","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T20:42:53Z","timestamp":1672260173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1159892.1159899"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1159892.1159899"],"URL":"https:\/\/doi.org\/10.1145\/1159892.1159899","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}