{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:37:18Z","timestamp":1759847838222,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,2,18]],"date-time":"2019-02-18T00:00:00Z","timestamp":1550448000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["JA 612 \/14-2"],"award-info":[{"award-number":["JA 612 \/14-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["JA 612 \/15-2"],"award-info":[{"award-number":["JA 612 \/15-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["JA 612\/20-1"],"award-info":[{"award-number":["JA 612\/20-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00224-019-09910-6","type":"journal-article","created":{"date-parts":[[2019,2,18]],"date-time":"2019-02-18T05:05:40Z","timestamp":1550466340000},"page":"120-140","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing"],"prefix":"10.1007","volume":"64","author":[{"given":"S\u00f6ren","family":"Henning","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5710-560X","authenticated-orcid":false,"given":"Malin","family":"Rau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Schmarje","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,2,18]]},"reference":[{"issue":"3","key":"9910_CR1","doi-asserted-by":"publisher","first-page":"14,1","DOI":"10.1145\/3092026","volume":"9","author":"A Adamaszek","year":"2017","unstructured":"Adamaszek, A., Kociumaka, T., Pilipczuk, M., Pilipczuk, M.: Hardness of approximation for strip packing. TOCT 9(3), 14,1\u201314,7 (2017). \nhttps:\/\/doi.org\/10.1145\/3092026","journal-title":"TOCT"},{"issue":"2","key":"9910_CR2","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/s00453-001-0076-9","volume":"32","author":"AK Amoura","year":"2002","unstructured":"Amoura, A.K., Bampis, E., Kenyon, C., Manoussakis, Y.: Scheduling independent multiprocessor tasks. Algorithmica 32(2), 247\u2013261 (2002). \nhttps:\/\/doi.org\/10.1007\/s00453-001-0076-9","journal-title":"Algorithmica"},{"issue":"4","key":"9910_CR3","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/0196-6774(81)90034-1","volume":"2","author":"BS Baker","year":"1981","unstructured":"Baker, B.S., Brown, D.J., Howard, P.K.: 5\/4 algorithm for two-dimensional packing. J. Algor. 2(4), 348\u2013368 (1981). \nhttps:\/\/doi.org\/10.1016\/0196-6774(81)90034-1","journal-title":"J. Algor."},{"issue":"4","key":"9910_CR4","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1137\/0209064","volume":"9","author":"BS Baker","year":"1980","unstructured":"Baker, B.S., Coffman, E.G. Jr., Rivest, R.L.: Orthogonal packings in two dimensions. SIAM J. Comput. 9(4), 846\u2013855 (1980). \nhttps:\/\/doi.org\/10.1137\/0209064","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9910_CR5","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1287\/moor.1050.0168","volume":"31","author":"N Bansal","year":"2006","unstructured":"Bansal, N., Correa, J\/R., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions Inapproximability results and approximation schemes. Math. Oper. Res. 31(1), 31\u201349 (2006). \nhttps:\/\/doi.org\/10.1287\/moor.1050.0168\n\n\n\nhttps:\/\/doi.org\/10.1287\/moor.1050.0168","journal-title":"Math. Oper. Res."},{"issue":"4","key":"9910_CR6","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1142\/S1793830911001413","volume":"3","author":"M Bougeret","year":"2011","unstructured":"Bougeret, M., Dutot, P.-F., Jansen, K., Robenek, C., Trystram, D.: Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms. Discret. Math. Algor. Appl. 3(4), 553\u2013586 (2011). \nhttps:\/\/doi.org\/10.1142\/S1793830911001413","journal-title":"Discret. Math. Algor. Appl."},{"key":"9910_CR7","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"Henrik I. Christensen","year":"2017","unstructured":"Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review. \nhttps:\/\/doi.org\/10.1016\/j.cosrev.2016.12.001\n\n (2017)","journal-title":"Computer Science Review"},{"issue":"4","key":"9910_CR8","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"EGJr Coffman","year":"1980","unstructured":"Coffman, E.G. Jr., Garey, M.R., Johnson, D.S., Tarjan, R.E.: Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput. 9(4), 808\u2013826 (1980). \nhttps:\/\/doi.org\/10.1137\/0209062","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9910_CR9","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1137\/0402042","volume":"2","author":"D Jianzhong","year":"1989","unstructured":"Jianzhong, D, Leung, J.Y.-T.: Complexity of scheduling parallel task systems. SIAM J. Discret. Math. 2(4), 473\u2013487 (1989). \nhttps:\/\/doi.org\/10.1137\/0402042","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"9910_CR10","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(94)90152-X","volume":"130","author":"A Feldmann","year":"1994","unstructured":"Feldmann, A., Sgall, J., Teng, S.-H.: Dynamic scheduling on parallel machines. Theor. Comput. Sci. 130(1), 49\u201372 (1994). \nhttps:\/\/doi.org\/10.1016\/0304-3975(94)90152-X","journal-title":"Theor. Comput. Sci."},{"key":"9910_CR11","doi-asserted-by":"publisher","unstructured":"Ga\u0307lvez, W., Grandoni, F., Ingala, S., Khan, A.: Improved pseudo-polynomial-time approximation for strip packing. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 9:1\u20139:14. \nhttps:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2016.9\n\n (2016)","DOI":"10.4230\/LIPIcs.FSTTCS.2016.9"},{"issue":"2","key":"9910_CR12","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1137\/0204015","volume":"4","author":"MR Garey","year":"1975","unstructured":"Garey, M.R., Graham, R.L.: Bounds for multiprocessor scheduling with resource constraints. SIAM J. Comput. 4(2), 187\u2013200 (1975). \nhttps:\/\/doi.org\/10.1137\/0204015","journal-title":"SIAM J. Comput."},{"key":"9910_CR13","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A guide to the theory of NP-completeness (1979)"},{"issue":"3","key":"9910_CR14","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1137\/0210042","volume":"10","author":"I Golan","year":"1981","unstructured":"Golan, I.: Performance bounds for orthogonal oriented two-dimensional packing algorithms. SIAM J. Comput. 10(3), 571\u2013582 (1981). \nhttps:\/\/doi.org\/10.1137\/0210042","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9910_CR15","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.comgeo.2013.08.008","volume":"47","author":"R Harren","year":"2014","unstructured":"Harren, R., Jansen, K., Pra\u0307del, L., Rob van, S.: A (5\/3 + \ud835\udf16)-approximation for strip packing. Comput. Geom. 47 (2), 248\u2013267 (2014). \nhttps:\/\/doi.org\/10.1016\/j.comgeo.2013.08.008","journal-title":"Comput. Geom."},{"key":"9910_CR16","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-03685-9_14","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Rolf Harren","year":"2009","unstructured":"Harren, R, van Stee, R.: Improved absolute approximation ratios for two-dimensional packing problems. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Volume 5687 of Lecture Notes in Computer Science, pp 177\u2013189. Springer (2009), \nhttps:\/\/doi.org\/10.1007\/978-3-642-03685-9_14"},{"key":"9910_CR17","doi-asserted-by":"publisher","unstructured":"Jansen, K.: A (3\/2+) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In: 24th ACM Symposium on Parallelism in Algorithms and Architectures, (SPAA), pp. 224\u2013235. \nhttps:\/\/doi.org\/10.1145\/2312005.2312048\n\n (2012)","DOI":"10.1145\/2312005.2312048"},{"key":"9910_CR18","doi-asserted-by":"publisher","unstructured":"Jansen, K., Land, F.: Scheduling monotone moldable jobs in linear time. In: 2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21-25, 2018, pp. 172\u2013181. \nhttps:\/\/doi.org\/10.1109\/IPDPS.2018.00027\n\n (2018)","DOI":"10.1109\/IPDPS.2018.00027"},{"issue":"3","key":"9910_CR19","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/s00453-001-0085-8","volume":"32","author":"K Jansen","year":"2002","unstructured":"Jansen, K., Porkolab, L.: Linear-time approximation schemes for scheduling malleable parallel tasks. Algorithmica 32(3), 507\u2013520 (2002). \nhttps:\/\/doi.org\/10.1007\/s00453-001-0085-8","journal-title":"Algorithmica"},{"key":"9910_CR20","unstructured":"Jansen, K., Rau, M.: Closing the gap for pseudo-polynomial strip packing. arXiv:\n1712.04922\n\n (2017)"},{"key":"9910_CR21","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-319-53925-6_32","volume-title":"WALCOM: Algorithms and Computation","author":"Klaus Jansen","year":"2017","unstructured":"Jansen, K., Rau, M.: Improved approximation for two dimensional strip packing with polynomial bounded width. In: WALCOM: Algorithms and Computation, Volume 10167 of LNCS, pp. 409\u2013420. \nhttps:\/\/doi.org\/10.1007\/978-3-319-53925-6_32\n\n (2017)"},{"issue":"3","key":"9910_CR22","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/j.disopt.2009.04.001","volume":"6","author":"K Jansen","year":"2009","unstructured":"Jansen, K., Solis-Oba, R.: Rectangle packing with one-dimensional resource augmentation. Discret. Optim. 6(3), 310\u2013323 (2009). \nhttps:\/\/doi.org\/10.1016\/j.disopt.2009.04.001","journal-title":"Discret. Optim."},{"issue":"8","key":"9910_CR23","doi-asserted-by":"publisher","first-page":"3571","DOI":"10.1137\/080736491","volume":"39","author":"K Jansen","year":"2010","unstructured":"Jansen, K., Tho\u0307le, R.: Approximation algorithms for scheduling parallel jobs. SIAM J. Comput. 39(8), 3571\u20133615 (2010). \nhttps:\/\/doi.org\/10.1137\/080736491","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9910_CR24","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1287\/moor.25.4.645.12118","volume":"25","author":"C Kenyon","year":"2000","unstructured":"Kenyon, C., R\u0117mila, E.: A near-optimal solution to a two-dimensional cutting stock problem. Math. Oper. Res. 25(4), 645\u2013656 (2000). \nhttps:\/\/doi.org\/10.1287\/moor.25.4.645.12118","journal-title":"Math. Oper. Res."},{"key":"9910_CR25","unstructured":"Ludwig, W., Tiwari, P.: Scheduling malleable and nonmalleable parallel tasks. In: 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 167\u2013176 (1994)"},{"key":"9910_CR26","doi-asserted-by":"publisher","unstructured":"Nadiradze, G., Wiese, A.: On approximating strip packing with a better ratio than 3\/2. In: 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1491\u20131510. \nhttps:\/\/doi.org\/10.1137\/1.9781611974331.ch102\n\n\n\nhttps:\/\/doi.org\/10.1137\/1.9781611974331.ch102\n\n (2016)","DOI":"10.1137\/1.9781611974331.ch102 10.1137\/1.9781611974331.ch102"},{"key":"9910_CR27","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/BFb0049416","volume-title":"Algorithms \u2014 ESA '94","author":"Ingo Schiermeyer","year":"1994","unstructured":"Schiermeyer, I: Reverse-fit: A 2-optimal algorithm for packing rectangles. In: 2nd Annual European Symposium on Algorithms (ESA) - Algorithms, pp. 290\u2013299. \nhttps:\/\/doi.org\/10.1007\/BFb0049416\n\n (1994)"},{"issue":"1","key":"9910_CR28","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(80)90121-0","volume":"10","author":"DD Sleator","year":"1980","unstructured":"Sleator, D.D.: A 2.5 times optimal algorithm for packing in two dimensions. Inf. Process. Lett. 10(1), 37\u201340 (1980). \nhttps:\/\/doi.org\/10.1016\/0020-0190(80)90121-0","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9910_CR29","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S0097539793255801","volume":"26","author":"A Steinberg","year":"1997","unstructured":"Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput. 26 (2), 401\u2013409 (1997). \nhttps:\/\/doi.org\/10.1137\/S0097539793255801","journal-title":"SIAM J. Comput."},{"issue":"1-2","key":"9910_CR30","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/j.ipl.2011.10.003","volume":"112","author":"M Sviridenko","year":"2012","unstructured":"Sviridenko, M.: A note on the kenyon-remila strip-packing algorithm. Inf. Process. Lett. 112(1-2), 10\u201312 (2012). \nhttps:\/\/doi.org\/10.1016\/j.ipl.2011.10.003","journal-title":"Inf. Process. Lett."},{"key":"9910_CR31","doi-asserted-by":"publisher","unstructured":"Turek, J., Wolf, J.L., Philip, S.: Approximate algorithms scheduling parallelizable tasks. In: 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 323\u2013332. \nhttps:\/\/doi.org\/10.1145\/140901.141909\n\n (1992)","DOI":"10.1145\/140901.141909"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09910-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09910-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09910-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,18]],"date-time":"2020-02-18T11:28:04Z","timestamp":1582025284000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09910-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,18]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["9910"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09910-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2019,2,18]]},"assertion":[{"value":"18 February 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}