{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T04:10:38Z","timestamp":1736136638106,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540309352"},{"type":"electronic","value":"9783540324263"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11602613_25","type":"book-chapter","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T08:24:24Z","timestamp":1133511864000},"page":"236-245","source":"Crossref","is-referenced-by-count":3,"title":["An Approximation Algorithm for Scheduling Malleable Tasks Under General Precedence Constraints"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hu","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/3-540-48311-X_39","volume-title":"Euro-Par\u201999 Parallel Processing","author":"E. Blayo","year":"1999","unstructured":"Blayo, E., Debrue, L., Mouni\u00e9, G., Trystram, D.: Dynamic load balancing for ocean circulation with adaptive meshing. In: Amestoy, P.R., Berger, P., Dayd\u00e9, M., Duff, I.S., Frayss\u00e9, V., Giraud, L., Ruiz, D. (eds.) Euro-Par 1999. LNCS, vol.\u00a01685, pp. 303\u2013312. Springer, Heidelberg (1999)"},{"issue":"11","key":"25_CR2","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/240455.240477","volume":"39","author":"D.E. Culler","year":"1996","unstructured":"Culler, D.E., Karp, R., Patterson, D., Sahay, A., Santos, E., Schauser, K., Subramonian, R., von Eicken, T.: LogP: A practical model of parallel computation. Communications of the ACM\u00a039(11), 78\u201385 (1996)","journal-title":"Communications of the ACM"},{"key":"25_CR3","volume-title":"Parallel computer architecture: A hardware\/software approach","author":"D.E. Culler","year":"1999","unstructured":"Culler, D.E., Singh, J.P., Gupta, A.: Parallel computer architecture: A hardware\/software approach. Morgan Kaufmann Publishers, San Francisco (1999)"},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1137\/0402042","volume":"2","author":"J. Du","year":"1989","unstructured":"Du, J., Leung, J.: Complexity of scheduling parallel task systems. SIAM Journal on Discrete Mathematics\u00a02, 473\u2013487 (1989)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"25_CR5","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"P.-F. Dutot","year":"2004","unstructured":"Dutot, P.-F., Mouni\u00e9, G., Trystram, D.: Scheduling parallel tasks \u2013 approximation algorithms. In: Leung, J.Y.-T. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton (2004)"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1287\/mnsc.7.2.167","volume":"7","author":"D.R. Fulkerson","year":"1961","unstructured":"Fulkerson, D.R.: A network flow computation for project cost curves. Management Science\u00a07, 167\u2013178 (1961)","journal-title":"Management Science"},{"key":"25_CR7","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1137\/0204015","volume":"4","author":"M. Garey","year":"1975","unstructured":"Garey, M., Graham, R.: Bounds for multiprocessor scheduling with resource constraints. SIAM Journal on Computing\u00a04, 187\u2013200 (1975)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR8","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R.L. Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell System Technical Journal\u00a045, 1563\u20131581 (1966)","journal-title":"Bell System Technical Journal"},{"issue":"2","key":"25_CR9","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1137\/0218016","volume":"18","author":"J.J. Hwang","year":"1989","unstructured":"Hwang, J.J., Chow, Y.C., Anger, F.D., Lee, C.Y.: Scheduling precedence graphs in systems with interprocessor communication times. SIAM Journal on Computing\u00a018(2), 244\u2013257 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1007\/3-540-45749-6_50","volume-title":"Algorithms - ESA 2002","author":"K. Jansen","year":"2002","unstructured":"Jansen, K.: Scheduling malleable parallel tasks: an asymptotic fully polynomial-time approximation scheme. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 562\u2013573. Springer, Heidelberg (2002)"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Jansen, K., Porkolab, L.: Linear-time approximation schemes for scheduling malleable parallel tasks. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999, pp. 490\u2013498 (1999)","DOI":"10.1145\/301250.301361"},{"key":"25_CR12","unstructured":"Jansen, K., Zhang, H.: Improved approximation algorithms for scheduling malleable tasks with precedence constraints. Technical Report, http:\/\/www.informatik.uni-kiel.de\/~hzh\/malle.ps"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Jansen, K., Zhang, H.: Scheduling malleable tasks with precedence constraints. In: Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2005, pp. 86\u201395 (2005)","DOI":"10.1145\/1073970.1073983"},{"issue":"9","key":"25_CR14","doi-asserted-by":"publisher","first-page":"1109","DOI":"10.1016\/S0167-8191(00)00031-4","volume":"26","author":"T. Kalinowski","year":"2000","unstructured":"Kalinowski, T., Kort, I., Trystram, D.: List scheduling of general task graphs under LogP. Parallel Computing\u00a026(9), 1109\u20131128 (2000)","journal-title":"Parallel Computing"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1287\/opre.9.3.296","volume":"9","author":"J.E. Kelley","year":"1961","unstructured":"Kelley, J.E.: Critical path planning and scheduling: mathematical bases. Operations Research\u00a09, 296\u2013320 (1961)","journal-title":"Operations Research"},{"key":"25_CR16","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J.K. Lenstra","year":"1978","unstructured":"Lenstra, J.K., Rinnooy Kan, A.H.G.: Complexity of scheduling under precedence constraints. Operations Research\u00a026, 22\u201335 (1978)","journal-title":"Operations Research"},{"issue":"2","key":"25_CR17","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1016\/S0377-2217(02)00264-3","volume":"142","author":"R. Lep\u00e8re","year":"2002","unstructured":"Lep\u00e8re, R., Mouni\u00e9, G., Trystram, D.: An approximation algorithm for scheduling trees of malleable tasks. European Journal of Operational Research\u00a0142(2), 242\u2013249 (2002)","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"25_CR18","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1142\/S0129054102001308","volume":"13","author":"R. Lep\u00e8re","year":"2002","unstructured":"Lep\u00e8re, R., Trystram, D., Woeginger, G.J.: Approximation algorithms for scheduling malleable tasks under precedence constraints. International Journal of Foundations of Computer Science\u00a013(4), 613\u2013627 (2002)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"25_CR19","unstructured":"Ludwig, W., Tiwari, P.: Scheduling malleable and nonmalleable parallel tasks. In: Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms, SODA 1994, pp. 167\u2013176 (1994)"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"Mouni\u00e9, G., Rapine, C., Trystram, D.: Efficient approximation algorithms for scheduling malleable tasks. In: Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1999, pp. 23\u201332 (1999)","DOI":"10.1145\/305619.305622"},{"key":"25_CR21","unstructured":"Mouni\u00e9, G., Rapine, C., Trystram, D.: A 3\/2-dual approximation algorithm for scheduling independent monotonic malleable tasks (manuscript)"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"Prasanna, G.N.S., Musicus, B.R.: Generalised multiprocessor scheduling using optimal control. In: Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1991, pp. 216\u2013228 (1991)","DOI":"10.1145\/113379.113399"},{"key":"25_CR23","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1287\/moor.23.4.909","volume":"23","author":"M. Skutella","year":"1998","unstructured":"Skutella, M.: Approximation algorithms for the discrete time-cost tradeoff problem. Mathematics of Operations Research\u00a023, 909\u2013929 (1998)","journal-title":"Mathematics of Operations Research"},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"Turel, J., Wolf, J., Yu, P.: Approximate algorithms for scheduling parallelizable tasks. In: Proceedings of the 4th Annual Symposium on Parallel Algorithms and Architectures, SPAA 1992, pp. 323\u2013332 (1992)","DOI":"10.1145\/140901.141909"},{"key":"25_CR25","unstructured":"Zhang, H.: Approximation Algorithms for Min-Max Resource Sharing and Malleable Tasks Scheduling. Ph.D. Thesis, University of Kiel, Germany (2004)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11602613_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T03:04:49Z","timestamp":1736132689000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11602613_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309352","9783540324263"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11602613_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}