{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:38:30Z","timestamp":1725493110928},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540440499"},{"type":"electronic","value":"9783540457060"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45706-2_29","type":"book-chapter","created":{"date-parts":[[2007,10,7]],"date-time":"2007-10-07T01:37:18Z","timestamp":1191721038000},"page":"225-233","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Non-approximability of the Bulk Synchronous Task Scheduling Problem"],"prefix":"10.1007","author":[{"given":"Noriyuki","family":"Fujimoto","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenichi","family":"Hagihara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,8,20]]},"reference":[{"issue":"4","key":"29_CR1","first-page":"345","volume":"26","author":"D.F. Bacon","year":"1994","unstructured":"Bacon, D.F. and Graham, S.L. and Sharp, O.J.: Compiler Transformations for High-Performance Computing, ACM computing surveys, Vol. 26, No. 4 (1994) 345\u2013420","journal-title":"Compiler Transformations for High-Performance Computing, ACM computing surveys"},{"issue":"1","key":"29_CR2","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1109\/71.655248","volume":"9","author":"S. Darbha","year":"1998","unstructured":"Darbha, S. and Agrawal, D. P.: Optimal Scheduling Algorithm for Distributed-Memory Machines, IEEE Trans. on Parallel and Distributed Systems, Vol. 9, No. 1 (1998) 87\u201395","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"key":"29_CR3","unstructured":"El-Rewini, H. and Lewis, T.G. and Ali, H.H.: TASK SCHEDULING in PARALLEL and DISTRIBUTED SYSTEMS, PTR Prentice Hall (1994)"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"Fujimoto, N. and Baba, T. and Hashimoto, T. and Hagihara, K.: A Task Scheduling Algorithm to Package Messages on Distributed Memory Parallel Machines, Proc. of 1999 Int. Symposium on Parallel Architectures, Algorithms, and Networks (1999) 236\u2013241","DOI":"10.1109\/ISPAN.1999.778945"},{"key":"29_CR5","unstructured":"Fujimoto, N. and Hashimoto, T. and Mori, M. and Hagihara, K.: On the Performance Gap between a Task Schedule and Its Corresponding Parallel Program, Proc. of 1999 Int. Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications, World Scientific (2000) 271\u2013287"},{"key":"29_CR6","unstructured":"Fujimoto, N. and Hagihara, K.: NP-Completeness of the Bulk Synchronous Task Scheduling Problem and Its Approximation Algorithm, Proc. of 2000 Int. Symposium on Parallel Architectures, Algorithms, and Networks (2000) 127\u2013132"},{"issue":"3","key":"29_CR7","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1142\/S0129054101000497","volume":"12","author":"N. Fujimoto","year":"2001","unstructured":"Fujimoto, N. and Baba, T. and Hashimoto, T. and Hagihara, K.: On Message Packaging in Task Scheduling for Distributed Memory Parallel Machines, The International Journal of Foundations of Computer Science, Vol. 12, No. 3 (2001) 285\u2013306","journal-title":"The International Journal of Foundations of Computer Science"},{"key":"29_CR8","volume-title":"Ph.D. diss.","author":"B. Kruatrachue","year":"1987","unstructured":"Kruatrachue, B., \u201cStatic task scheduling and packing in parallel processing systems\u201d, Ph.D. diss., Department of Electrical and Computer Engineering, Oregon State University, Corvallis, 1987"},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0167-6377(94)90024-8","volume":"16","author":"J. A. Hoogeveen","year":"1994","unstructured":"Hoogeveen, J. A., Lenstra, J. K., and Veltman, B.: \u201cThree, Four, Five, Six or the Complexity of Scheduling with Communication Delays\u201d, Oper. Res. Lett. Vol. 16 (1994) 129\u2013137","journal-title":"Oper. Res. Lett."},{"key":"29_CR10","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. and Rinnooy Kan, A. H. G.: Complexity of Scheduling under Precedence Constraints, Operations Research, Vol. 26 (1978) 22\u201335","journal-title":"Operations Research"},{"key":"29_CR11","unstructured":"Lenstra, J.K. and Shmoys, D. B.: Computing Near-Optimal Schedules, Scheduling Theory and its Applications, John Wiley & Sons (1995) 1\u201314"},{"issue":"1","key":"29_CR12","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1109\/71.481597","volume":"7","author":"M. A. Palis","year":"1996","unstructured":"Palis, M. A. and Liou, J. and Wei, D. S. L.: Task Clustering and Scheduling for Distributed Memory Parallel Architectures, IEEE Trans. on Parallel and Distributed Systems, Vol. 7, No. 1 (1996) 46\u201355","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"issue":"2","key":"29_CR13","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1137\/0219021","volume":"19","author":"C. H. Papadimitriou","year":"1990","unstructured":"Papadimitriou, C. H. and Yannakakis, M.: Towards An Architecture-Independent Analysis of Parallel Algorithms, SIAM J. Comput., Vol. 19, No. 2 (1990) 322\u2013328","journal-title":"SIAM J. Comput."},{"key":"29_CR14","first-page":"229","volume":"3","author":"R. Thurimella","year":"1992","unstructured":"Thurimella, R. and Yesha, Y.: A scheduling principle for precedence graphs with communication delay, Int. Conf. on Parallel Processing, Vol. 3 (1992) 229\u2013236","journal-title":"Int. Conf. on Parallel Processing"},{"issue":"8","key":"29_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"L.G. Valiant","year":"1990","unstructured":"Valiant, L.G.: A Bridging Model for Parallel Computation, Communications of the ACM, Vol. 33, No. 8 (1990) 103\u2013111","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2002 Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45706-2_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,19]],"date-time":"2020-04-19T20:19:41Z","timestamp":1587327581000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45706-2_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540440499","9783540457060"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-45706-2_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"20 August 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}