{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,28]],"date-time":"2025-07-28T21:49:13Z","timestamp":1753739353897,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T00:00:00Z","timestamp":1683676800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T00:00:00Z","timestamp":1683676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200020B_182865\/1"],"award-info":[{"award-number":["200020B_182865\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ANID, Subvenci\u00f3n a la Instalaci\u00f3n Acad\u00e9mica","award":["85220118"],"award-info":[{"award-number":["85220118"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,10]]},"DOI":"10.1007\/s00453-023-01130-2","type":"journal-article","created":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T06:08:00Z","timestamp":1683785280000},"page":"3088-3109","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Tight $$(3\/2+\\varepsilon )$$-Approximation for Skewed Strip Packing"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6395-3322","authenticated-orcid":false,"given":"Waldo","family":"G\u00e1lvez","sequence":"first","affiliation":[]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[]},{"given":"Afrouz Jabal","family":"Ameli","sequence":"additional","affiliation":[]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[]},{"given":"Arindam","family":"Khan","sequence":"additional","affiliation":[]},{"given":"Malin","family":"Rau","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,10]]},"reference":[{"issue":"3","key":"1130_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. ACM Trans. Comput. Theory 9(3), 14:1-14:7 (2017). https:\/\/doi.org\/10.1145\/3092026","journal-title":"ACM Trans. Comput. Theory"},{"key":"1130_CR2","doi-asserted-by":"publisher","unstructured":"Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 400\u2013409. IEEE Computer Society (2013). https:\/\/doi.org\/10.1109\/FOCS.2013.50","DOI":"10.1109\/FOCS.2013.50"},{"key":"1130_CR3","doi-asserted-by":"publisher","unstructured":"Adamaszek, A., Wiese, A.: A quasi-ptas for the two-dimensional geometric knapsack problem. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1491\u20131505. SIAM (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.98","DOI":"10.1137\/1.9781611973730.98"},{"issue":"4","key":"1130_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). https:\/\/doi.org\/10.1137\/0209064","journal-title":"SIAM J. Comput."},{"key":"1130_CR5","doi-asserted-by":"publisher","unstructured":"Bansal, N., Caprara, A., Jansen, K., Pr\u00e4del, L., Sviridenko, M.: A structural lemma in 2-dimensional packing, and its implications on approximability. In: Algorithms and Computation, 20th International Symposium (ISAAC), vol. 5878, pp. 77\u201386. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-10631-6_10","DOI":"10.1007\/978-3-642-10631-6_10"},{"issue":"1","key":"1130_CR6","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). https:\/\/doi.org\/10.1287\/moor.1050.0168","journal-title":"Math. Oper. Res."},{"key":"1130_CR7","doi-asserted-by":"publisher","unstructured":"Bansal, N., Khan, A.: Improved approximation algorithm for two-dimensional bin packing. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 13\u201325. SIAM (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.2","DOI":"10.1137\/1.9781611973402.2"},{"key":"1130_CR8","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 892\u2013901. SIAM (2009). http:\/\/dl.acm.org\/citation.cfm?id=1496770.1496867","DOI":"10.1137\/1.9781611973068.97"},{"issue":"2","key":"1130_CR9","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00454-012-9417-5","volume":"48","author":"TM Chan","year":"2012","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discrete Comput. Geom. 48(2), 373\u2013392 (2012). https:\/\/doi.org\/10.1007\/s00454-012-9417-5","journal-title":"Discrete Comput. Geom."},{"key":"1130_CR10","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). https:\/\/doi.org\/10.1016\/j.cosrev.2016.12.001","journal-title":"Comput. Sci. Rev."},{"key":"1130_CR11","volume-title":"Computer and Job-Shop Scheduling Theory","author":"EG Coffman","year":"1976","unstructured":"Coffman, E.G., Bruno, J.L.: Computer and Job-Shop Scheduling Theory. Wiley, New York (1976)"},{"key":"1130_CR12","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-1-4419-7997-1_35","volume-title":"Bin Packing Approximation Algorithms: Survey and Classification","author":"EG Coffman Jr","year":"2013","unstructured":"Coffman, E.G., Jr., Csirik, J., Galambos, G., Martello, S., Vigo, D.: Bin Packing Approximation Algorithms: Survey and Classification, pp. 455\u2013531. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4419-7997-1_35"},{"issue":"4","key":"1130_CR13","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"EG Coffman Jr","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). https:\/\/doi.org\/10.1137\/0209062","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1130_CR14","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1145\/1150334.1150339","volume":"2","author":"L Epstein","year":"2006","unstructured":"Epstein, L., van Stee, R.: This side up! ACM Trans. Algorithms 2(2), 228\u2013243 (2006). https:\/\/doi.org\/10.1145\/1150334.1150339","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"1130_CR15","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"MR Garey","year":"1978","unstructured":"Garey, M.R., Johnson, D.S.: \u201cstrong\u2019\u2019 np-completeness results: motivation, examples, and implications. J. ACM 25(3), 499\u2013508 (1978). https:\/\/doi.org\/10.1145\/322077.322090","journal-title":"J. ACM"},{"issue":"4","key":"1130_CR16","doi-asserted-by":"publisher","first-page":"33:1","DOI":"10.1145\/3473713","volume":"17","author":"W G\u00e1lvez","year":"2021","unstructured":"G\u00e1lvez, W., Grandoni, F., Ingala, S., Heydrich, S., Khan, A., Wiese, A.: Approximating geometric knapsack via L-packings. ACM Trans. Algorithms 17(4), 33:1-33:67 (2021). https:\/\/doi.org\/10.1145\/3473713","journal-title":"ACM Trans. Algorithms"},{"key":"1130_CR17","doi-asserted-by":"publisher","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), vol.\u00a065, pp. 9:1\u20139:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2016.9","DOI":"10.4230\/LIPIcs.FSTTCS.2016.9"},{"key":"1130_CR18","doi-asserted-by":"publisher","unstructured":"G\u00e1lvez, W., Grandoni, F., Khan, A., Ram\u00edrez-Romero, D., Wiese, A.: Improved approximation algorithms for 2-dimensional knapsack: packing into multiple l-shapes, spirals, and more. In: 37th International Symposium on Computational Geometry (SoCG), vol. 189, pp. 39:1\u201339:17 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2021.39","DOI":"10.4230\/LIPIcs.SoCG.2021.39"},{"issue":"2","key":"1130_CR19","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 + \\varepsilon )$$-approximation for strip packing. Comput. Geom. 47(2), 248\u2013267 (2014). https:\/\/doi.org\/10.1016\/j.comgeo.2013.08.008","journal-title":"Comput. Geom."},{"key":"1130_CR20","doi-asserted-by":"publisher","unstructured":"Harren, R., van Stee, R.: Improved absolute approximation ratios for two-dimensional packing problems. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop (APPROX\/RANDOM), vol. 5687, pp. 177\u2013189. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-03685-9_14","DOI":"10.1007\/978-3-642-03685-9_14"},{"issue":"1","key":"1130_CR21","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s00224-019-09910-6","volume":"64","author":"S Henning","year":"2020","unstructured":"Henning, S., Jansen, K., Rau, M., Schmarje, L.: Complexity and inapproximability results for parallel task scheduling and strip packing. Theory Comput. Syst. 64(1), 120\u2013140 (2020). https:\/\/doi.org\/10.1007\/s00224-019-09910-6","journal-title":"Theory Comput. Syst."},{"key":"1130_CR22","doi-asserted-by":"publisher","unstructured":"Jansen, K., Pr\u00e4del, L.: A new asymptotic approximation algorithm for 3-dimensional strip packing. In: 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), vol. 8327, pp. 327\u2013338. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-04298-5_29","DOI":"10.1007\/978-3-319-04298-5_29"},{"key":"1130_CR23","doi-asserted-by":"publisher","unstructured":"Jansen, K., Rau, M.: Closing the gap for pseudo-polynomial strip packing. In: 27th Annual European Symposium on Algorithms (ESA), vol. 144, pp. 62:1\u201362:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.62","DOI":"10.4230\/LIPIcs.ESA.2019.62"},{"key":"1130_CR24","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.tcs.2019.04.002","volume":"789","author":"K Jansen","year":"2019","unstructured":"Jansen, K., Rau, M.: Improved approximation for two dimensional strip packing with polynomial bounded width. Theor. Comput. Sci. 789, 34\u201349 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2019.04.002","journal-title":"Theor. Comput. Sci."},{"key":"1130_CR25","doi-asserted-by":"publisher","unstructured":"Jansen, K., Solis-Oba, R.: New approximability results for 2-dimensional packing problems. In: Mathematical Foundations of Computer Science, 32nd International Symposium (MFCS), vol. 4708, pp. 103\u2013114. Springer (2007). https:\/\/doi.org\/10.1007\/978-3-540-74456-6_11","DOI":"10.1007\/978-3-540-74456-6_11"},{"key":"1130_CR26","doi-asserted-by":"publisher","unstructured":"Jansen, K., van Stee, R.: On strip packing with rotations. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 755\u2013761. ACM (2005). https:\/\/doi.org\/10.1145\/1060590.1060702","DOI":"10.1145\/1060590.1060702"},{"issue":"3","key":"1130_CR27","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s00453-006-0194-5","volume":"47","author":"K Jansen","year":"2007","unstructured":"Jansen, K., Zhang, G.: Maximizing the total profit of rectangles packed into a rectangle. Algorithmica 47(3), 323\u2013342 (2007). https:\/\/doi.org\/10.1007\/s00453-006-0194-5","journal-title":"Algorithmica"},{"key":"1130_CR28","doi-asserted-by":"publisher","unstructured":"Karbasioun, M.M., Shaikhet, G., Kranakis, E., Lambadaris, I.: Power strip packing of malleable demands in smart grid. In: Proceedings of IEEE International Conference on Communications (ICC), pp. 4261\u20134265. IEEE (2013). https:\/\/doi.org\/10.1109\/ICC.2013.6655233","DOI":"10.1109\/ICC.2013.6655233"},{"issue":"4","key":"1130_CR29","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). https:\/\/doi.org\/10.1287\/moor.25.4.645.12118","journal-title":"Math. Oper. Res."},{"key":"1130_CR30","unstructured":"Khan, A.: Approximation algorithms for multidimensional bin packing. Ph.D. thesis, Georgia Institute of Technology, Atlanta, GA, USA (2016). http:\/\/hdl.handle.net\/1853\/54371"},{"key":"1130_CR31","doi-asserted-by":"publisher","unstructured":"Khan, A., Maiti, A., Sharma, A., Wiese, A.: On guillotine separable packings for the two-dimensional geometric knapsack problem. In: 37th International Symposium on Computational Geometry (SoCG), vol. 189, pp. 48:1\u201348:17 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2021.48","DOI":"10.4230\/LIPIcs.SoCG.2021.48"},{"key":"1130_CR32","doi-asserted-by":"publisher","unstructured":"Khan, A., Pittu, M.R.: On guillotine separability of squares and rectangles. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2020), vol. 176, pp. 47:1\u201347:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2020.47","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.47"},{"issue":"3","key":"1130_CR33","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0743-7315(90)90019-L","volume":"10","author":"JY Leung","year":"1990","unstructured":"Leung, J.Y., Tam, T.W., Wong, C.S., Young, G.H., Chin, F.Y.L.: Packing squares into a square. J. Parallel Distrib. Comput. 10(3), 271\u2013275 (1990). https:\/\/doi.org\/10.1016\/0743-7315(90)90019-L","journal-title":"J. Parallel Distrib. Comput."},{"key":"1130_CR34","doi-asserted-by":"publisher","unstructured":"Mitchell, J.S.B.: Approximating maximum independent set for rectangles in the plane. In: 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 339\u2013350 (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00042","DOI":"10.1109\/FOCS52979.2021.00042"},{"key":"1130_CR35","doi-asserted-by":"publisher","unstructured":"Miyazawa, F.K., Wakabayashi, Y.: Packing problems with orthogonal rotations. In: Theoretical Informatics, 6th Latin American Symposium (LATIN), vol. 2976, pp. 359\u2013368. Springer (2004). https:\/\/doi.org\/10.1007\/978-3-540-24698-5_40","DOI":"10.1007\/978-3-540-24698-5_40"},{"key":"1130_CR36","doi-asserted-by":"publisher","unstructured":"Nadiradze, G., Wiese, A.: On approximating strip packing with a better ratio than 3\/2. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1491\u20131510. SIAM (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch102","DOI":"10.1137\/1.9781611974331.ch102"},{"key":"1130_CR37","doi-asserted-by":"publisher","unstructured":"Schiermeyer, I.: Reverse-fit: A 2-optimal algorithm for packing rectangles. In: Algorithms, Second Annual European Symposium (ESA), vol. 855, pp. 290\u2013299. Springer (1994). https:\/\/doi.org\/10.1007\/BFb0049416","DOI":"10.1007\/BFb0049416"},{"issue":"1","key":"1130_CR38","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). https:\/\/doi.org\/10.1016\/0020-0190(80)90121-0","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1130_CR39","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). https:\/\/doi.org\/10.1137\/S0097539793255801","journal-title":"SIAM J. Comput."},{"key":"1130_CR40","doi-asserted-by":"publisher","unstructured":"Tang, S., Huang, Q., Li, X., Wu, D.: Smoothing the energy consumption: peak demand reduction in smart grid. In: 32nd IEEE International Conference on Computer Communications (INFOCOM), pp. 1133\u20131141. IEEE (2013). https:\/\/doi.org\/10.1109\/INFCOM.2013.6566904","DOI":"10.1109\/INFCOM.2013.6566904"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01130-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01130-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01130-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T14:08:13Z","timestamp":1695737293000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01130-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,10]]},"references-count":40,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["1130"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01130-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,5,10]]},"assertion":[{"value":"22 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}