{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:57Z","timestamp":1759638057603,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319905297"},{"type":"electronic","value":"9783319905303"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","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":[[2018]]},"DOI":"10.1007\/978-3-319-90530-3_15","type":"book-chapter","created":{"date-parts":[[2018,4,24]],"date-time":"2018-04-24T07:23:53Z","timestamp":1524554633000},"page":"169-180","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing"],"prefix":"10.1007","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"}]},{"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":[[2018,4,25]]},"reference":[{"issue":"4","key":"15_CR1","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1137\/0402042","volume":"2","author":"J Du","year":"1989","unstructured":"Du, J., Leung, J.Y.: Complexity of scheduling parallel task systems. SIAM J. Discrete Math. 2(4), 473\u2013487 (1989)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"15_CR2","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)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"15_CR3","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)","journal-title":"TOCT"},{"key":"15_CR4","unstructured":"Jansen, K., Rau, M.: Closing the gap for pseudo-polynomial strip packing. CoRR abs\/1705.04587 (2017)"},{"key":"15_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-319-53925-6_32","volume-title":"WALCOM: Algorithms and Computation","author":"K Jansen","year":"2017","unstructured":"Jansen, K., Rau, M.: Improved approximation for two dimensional strip packing with polynomial bounded width. In: Poon, S.-H., Rahman, M.S., Yen, H.-C. (eds.) WALCOM 2017. LNCS, vol. 10167, pp. 409\u2013420. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-53925-6_32"},{"key":"15_CR6","unstructured":"G\u00e1lvez, 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 (2016)"},{"key":"15_CR7","doi-asserted-by":"crossref","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 (2016)","DOI":"10.1137\/1.9781611974331.ch102"},{"issue":"8","key":"15_CR8","doi-asserted-by":"publisher","first-page":"3571","DOI":"10.1137\/080736491","volume":"39","author":"K Jansen","year":"2010","unstructured":"Jansen, K., Th\u00f6le, R.: Approximation algorithms for scheduling parallel jobs. SIAM J. Comput. 39(8), 3571\u20133615 (2010)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"15_CR9","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)","journal-title":"Algorithmica"},{"issue":"3","key":"15_CR10","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)","journal-title":"Algorithmica"},{"issue":"2","key":"15_CR11","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)","journal-title":"SIAM J. Comput."},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Turek, J., Wolf, J.L., Yu, P.S.: Approximate algorithms scheduling parallelizable tasks. In: 4th annual ACM symposium on Parallel algorithms and architectures (SPAA), pp. 323\u2013332 (1992)","DOI":"10.1145\/140901.141909"},{"key":"15_CR13","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)"},{"issue":"1","key":"15_CR14","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.: Dynamic scheduling on parallel machines. Theor. Comput. Sci. 130(1), 49\u201372 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Jansen, K.: A $$(3\/2+\\varepsilon )$$ approximation algorithm for scheduling moldable and non-moldable parallel tasks. In: 24th ACM Symposium on Parallelism in Algorithms and Architectures, (SPAA), pp. 224\u2013235 (2012)","DOI":"10.1145\/2312005.2312048"},{"issue":"4","key":"15_CR16","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1137\/0209064","volume":"9","author":"BS Baker Jr","year":"1980","unstructured":"Baker Jr., B.S., Coffman, E.G., Rivest, R.L.: Orthogonal packings in two dimensions. SIAM J. Comput. 9(4), 846\u2013855 (1980)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"15_CR17","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"EG Coffman Jr","year":"1980","unstructured":"Coffman Jr., E.G., 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)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"15_CR18","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. Proc. Lett. 10(1), 37\u201340 (1980)","journal-title":"Inf. Proc. Lett."},{"key":"15_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/BFb0049416","volume-title":"Algorithms \u2014 ESA 1994","author":"I Schiermeyer","year":"1994","unstructured":"Schiermeyer, I.: Reverse-fit: A 2-optimal algorithm for packing rectangles. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 290\u2013299. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/BFb0049416"},{"issue":"2","key":"15_CR20","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)","journal-title":"SIAM J. Comput."},{"key":"15_CR21","series-title":"Lecture Notes in Computer Science","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":"R Harren","year":"2009","unstructured":"Harren, R., van Stee, R.: Improved absolute approximation ratios for two-dimensional packing problems. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX\/RANDOM -2009. LNCS, vol. 5687, pp. 177\u2013189. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03685-9_14"},{"issue":"2","key":"15_CR22","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., Pr\u00e4del, L., van Stee, R.: A (5\/3 + $$\\epsilon $$)-approximation for strip packing. Comput. Geom. 47(2), 248\u2013267 (2014)","journal-title":"Comput. Geom."},{"issue":"3","key":"15_CR23","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)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"15_CR24","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., Katseff, H.P.: A 5\/4 algorithm for two-dimensional packing. J. Algorithms 2(4), 348\u2013368 (1981)","journal-title":"J. Algorithms"},{"issue":"4","key":"15_CR25","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\u00e9mila, E.: A near-optimal solution to a two-dimensional cutting stock problem. Math. Oper. Res. 25(4), 645\u2013656 (2000)","journal-title":"Math. Oper. Res."},{"issue":"1\u20132","key":"15_CR26","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. Proc. Lett. 112(1\u20132), 10\u201312 (2012)","journal-title":"Inf. Proc. Lett."},{"issue":"4","key":"15_CR27","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1142\/S1793830911001413","volume":"3","author":"M Bougeret","year":"2011","unstructured":"Bougeret, M., Dutot, P., Jansen, K., Robenek, C., Trystram, D.: Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms. Discrete Math. Algorithms Appl. 3(4), 553\u2013586 (2011)","journal-title":"Discrete Math. Algorithms Appl."},{"issue":"3","key":"15_CR28","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. Discrete Optim. 6(3), 310\u2013323 (2009)","journal-title":"Discrete Optim."},{"key":"15_CR29","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"HI Christensen","year":"2017","unstructured":"Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63\u201379 (2017)","journal-title":"Comput. Sci. Rev."},{"key":"15_CR30","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"15_CR31","doi-asserted-by":"crossref","unstructured":"Henning, S., Jansen, K., Rau, M., Schmarje, L.: Complexity and inapproximability results for parallel task scheduling and strip packing. CoRR abs\/1705.04587 (2017)","DOI":"10.1007\/978-3-319-90530-3_15"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-90530-3_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T11:30:17Z","timestamp":1710243017000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-90530-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319905297","9783319905303"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-90530-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"25 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Moscow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}