{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T15:47:31Z","timestamp":1771861651076,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T00:00:00Z","timestamp":1690416000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T00:00:00Z","timestamp":1690416000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Google CSExplore Award"},{"name":"Google India Research Award"},{"name":"Pratiksha Trust Young Investigator Award"},{"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"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["JA 612 \/25-1"],"award-info":[{"award-number":["JA 612 \/25-1"]}],"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"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["JA 612 \/25-1"],"award-info":[{"award-number":["JA 612 \/25-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["JA 612 \/20-1"],"award-info":[{"award-number":["JA 612 \/20-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["JA 612 \/25-1"],"award-info":[{"award-number":["JA 612 \/25-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the Non-preemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Non-preemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a<jats:inline-formula><jats:alternatives><jats:tex-math>$$(5\/3+\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mn>5<\/mml:mn><mml:mo>\/<\/mml:mo><mml:mn>3<\/mml:mn><mml:mo>+<\/mml:mo><mml:mi>\u03b5<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption<jats:inline-formula><jats:alternatives><jats:tex-math>$$(1+\\varepsilon ) {\\textrm{OPT}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>+<\/mml:mo><mml:mi>\u03b5<\/mml:mi><mml:mo>)<\/mml:mo><mml:mtext>OPT<\/mml:mtext><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The remaining jobs fit into a thin container of height 1. This AEPTAS is used as a subroutine to acquire the<jats:inline-formula><jats:alternatives><jats:tex-math>$$(5\/3+\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mn>5<\/mml:mn><mml:mo>\/<\/mml:mo><mml:mn>3<\/mml:mn><mml:mo>+<\/mml:mo><mml:mi>\u03b5<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation algorithm. The previous best result for NPDM was a 2.7-approximation based on FFDH (Ranjan et al., in: 2015 IEEE symposium on computers and communication (ISCC), pp 758\u2013763, IEEE, 2015). One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg\u2019s algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above, such that it does not exceed the bound of<jats:inline-formula><jats:alternatives><jats:tex-math>$$(5\/3+\\varepsilon ) {\\textrm{OPT}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mn>5<\/mml:mn><mml:mo>\/<\/mml:mo><mml:mn>3<\/mml:mn><mml:mo>+<\/mml:mo><mml:mi>\u03b5<\/mml:mi><mml:mo>)<\/mml:mo><mml:mtext>OPT<\/mml:mtext><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00453-023-01152-w","type":"journal-article","created":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T12:02:23Z","timestamp":1690459343000},"page":"3649-3679","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Peak Demand Minimization via Sliced Strip Packing"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3083-7998","authenticated-orcid":false,"given":"Max A.","family":"Deppert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arindam","family":"Khan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Malin","family":"Rau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Malte","family":"Tutas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,27]]},"reference":[{"key":"1152_CR1","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"},{"issue":"02","key":"1152_CR2","doi-asserted-by":"publisher","first-page":"1850025","DOI":"10.1142\/S1793830918500258","volume":"10","author":"MM Karbasioun","year":"2018","unstructured":"Karbasioun, M.M., Shaikhet, G., Lambadaris, I., Kranakis, E.: Asymptotically optimal scheduling of random malleable demands in smart grid. Discrete Math. Algorithms Appl. 10(02), 1850025 (2018)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"1152_CR3","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1016\/j.rser.2013.10.022","volume":"30","author":"P Siano","year":"2014","unstructured":"Siano, P.: Demand response and smart grids\u2014a survey. Renew. Sustain. Energy Rev. 30, 461\u2013478 (2014)","journal-title":"Renew. Sustain. Energy Rev."},{"key":"1152_CR4","doi-asserted-by":"crossref","unstructured":"Alamdari, S., Biedl, T., Chan, T.M., Grant, E., Jampani, K.R., Keshav, S., Lubiw, A., Pathak, V.: Smart-grid electricity allocation via strip packing with slicing. In: Workshop on Algorithms and Data Structures, pp. 25\u201336. Springer (2013)","DOI":"10.1007\/978-3-642-40104-6_3"},{"key":"1152_CR5","unstructured":"Liu, F.-H., Liu, H.-H., Wong, P.W.: Optimal nonpreemptive scheduling in a smart grid model. In: 27th International Symposium on Algorithms and Computation (ISAAC 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"key":"1152_CR6","doi-asserted-by":"crossref","unstructured":"Ranjan, A., Khargonekar, P., Sahni, S.: Offline preemptive scheduling of power demands to minimize peak power in smart grids. In: 2014 IEEE Symposium on Computers and Communications (ISCC), pp. 1\u20136. IEEE (2014)","DOI":"10.1109\/ISCC.2014.6912525"},{"key":"1152_CR7","doi-asserted-by":"crossref","unstructured":"Ranjan, A., Khargonekar, P., Sahni, S.: Smart grid power scheduling via bottom left decreasing height packing. In: 2016 IEEE Symposium on Computers and Communication (ISCC), pp. 1128\u20131133. IEEE (2016)","DOI":"10.1109\/ISCC.2016.7543888"},{"issue":"8","key":"1152_CR8","doi-asserted-by":"publisher","first-page":"3447","DOI":"10.1109\/TII.2017.2781284","volume":"14","author":"N Chakraborty","year":"2017","unstructured":"Chakraborty, N., Mondal, A., Mondal, S.: Efficient scheduling of nonpreemptive appliances for peak load optimization in smart grid. IEEE Trans. Ind. Inf. 14(8), 3447\u20133458 (2017)","journal-title":"IEEE Trans. Ind. Inf."},{"issue":"4","key":"1152_CR9","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."},{"issue":"4","key":"1152_CR10","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":"1","key":"1152_CR11","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":"1152_CR12","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":"1152_CR13","doi-asserted-by":"publisher","unstructured":"Schiermeyer, I.: Reverse-fit: a 2-optimal algorithm for packing rectangles. In: van Leeuwen, J. (ed.) Algorithms\u2014ESA \u201994, Second Annual European Symposium, Utrecht, Proceedings. Lecture Notes in Computer Science, vol. 855, pp. 290\u2013299. Springer (1994). https:\/\/doi.org\/10.1007\/BFb0049416","DOI":"10.1007\/BFb0049416"},{"key":"1152_CR14","doi-asserted-by":"publisher","unstructured":"Harren, R., van Stee, R.: Improved absolute approximation ratios for two-dimensional packing problems. In: Dinur, I., Jansen, K., Naor, J., Rolim, J.D.P. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley. Proceedings. Lecture Notes in Computer Science, 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"},{"key":"1152_CR15","doi-asserted-by":"crossref","unstructured":"Harren, R., Jansen, K., Pr\u00e4del, L., van Stee, R.: A (5\/3 + eps)-approximation for 2d strip packing. In: Brieden, A., G\u00f6rg\u00fcl\u00fc, Z., Krug, T., Kropat, E., Meyer-Nieberg, S., Mihelcic, G., Pickl, S.W. (eds.) 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Munich. Extended Abstracts, pp. 139\u2013 142 (2012)","DOI":"10.1007\/978-3-642-22300-6_40"},{"key":"1152_CR16","doi-asserted-by":"crossref","unstructured":"Ranjan, A., Khargonekar, P., Sahni, S.: Offline first fit scheduling in smart grids. In: 2015 IEEE Symposium on Computers and Communication (ISCC), pp. 758\u2013763. IEEE (2015)","DOI":"10.1109\/ISCC.2015.7405605"},{"key":"1152_CR17","doi-asserted-by":"crossref","unstructured":"Yaw, S., Mumey, B., McDonald, E., Lemke, J.: Peak demand scheduling in the smart grid. In: 2014 IEEE International Conference on Smart Grid Communications (SmartGridComm), pp. 770\u2013775. IEEE (2014)","DOI":"10.1109\/SmartGridComm.2014.7007741"},{"issue":"5","key":"1152_CR18","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s10951-015-0427-z","volume":"18","author":"I B\u0142\u0105dek","year":"2015","unstructured":"B\u0142\u0105dek, I., Drozdowski, M., Guinand, F., Schepler, X.: On contiguous and non-contiguous parallel task scheduling. J. Sched. 18(5), 487\u2013495 (2015)","journal-title":"J. Sched."},{"key":"1152_CR19","unstructured":"G\u00e1lvez, W., Grandoni, F., Ameli, A.J., Khodamoradi, K.: Approximation algorithms for demand strip packing. CoRR arXiv:2105.08577 (2021)"},{"issue":"4","key":"1152_CR20","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."},{"issue":"3","key":"1152_CR21","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). https:\/\/doi.org\/10.1016\/j.disopt.2009.04.001","journal-title":"Discret. Optim."},{"key":"1152_CR22","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":"1152_CR23","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. 65, pp. 9\u2013 1914. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2016.9","DOI":"10.4230\/LIPIcs.FSTTCS.2016.9"},{"issue":"3","key":"1152_CR24","doi-asserted-by":"publisher","first-page":"14","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\u20131147 (2017). https:\/\/doi.org\/10.1145\/3092026","journal-title":"ACM Trans. Comput. Theory"},{"issue":"1","key":"1152_CR25","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":"1152_CR26","unstructured":"Jansen, K., Rau, M.: Closing the gap for pseudo-polynomial strip packing. In: ESA, vol. 144, pp. 62\u201316214 (2019)"},{"key":"1152_CR27","unstructured":"G\u00e1lvez, W., Grandoni, F., Ameli, A.J., Jansen, K., Khan, A., Rau, M.: A tight (3\/2+$$\\epsilon $$) approximation for skewed strip packing. In: Byrka, J., Meka, R. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2020, Virtual Conference. LIPIcs, vol. 176, pp. 44\u201314418 (2020)"},{"key":"1152_CR28","doi-asserted-by":"crossref","unstructured":"Bougeret, M., Dutot, P.F., Jansen, K., Otte, C., Trystram, D.: Approximating the non-contiguous multiple organization packing problem. In: IFIP International Conference on Theoretical Computer Science, pp. 316\u2013327. Springer (2010)","DOI":"10.1007\/978-3-642-15240-5_23"},{"issue":"1","key":"1152_CR29","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00453-003-1078-6","volume":"39","author":"K Jansen","year":"2004","unstructured":"Jansen, K.: Scheduling malleable parallel tasks: An asymptotic fully polynomial time approximation scheme. Algorithmica 39(1), 59\u201381 (2004)","journal-title":"Algorithmica"},{"issue":"8","key":"1152_CR30","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). https:\/\/doi.org\/10.1137\/080736491","journal-title":"SIAM J. Comput."},{"key":"1152_CR31","doi-asserted-by":"crossref","unstructured":"Jansen, K.: A (3\/2+ $$\\varepsilon $$) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 224\u2013235 (2012)","DOI":"10.1145\/2312005.2312048"},{"key":"1152_CR32","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, pp. 172\u2013181. IEEE Computer Society (2018). https:\/\/doi.org\/10.1109\/IPDPS.2018.00027","DOI":"10.1109\/IPDPS.2018.00027"},{"issue":"4","key":"1152_CR33","doi-asserted-by":"publisher","first-page":"1256","DOI":"10.1137\/080736831","volume":"39","author":"N Bansal","year":"2009","unstructured":"Bansal, N., Caprara, A., Sviridenko, M.: A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM J. Comput. 39(4), 1256\u20131278 (2009). https:\/\/doi.org\/10.1137\/080736831","journal-title":"SIAM J. Comput."},{"key":"1152_CR34","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\u2013 338. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-04298-5_29","DOI":"10.1007\/978-3-319-04298-5_29"},{"issue":"1","key":"1152_CR35","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":"1152_CR36","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khan, A.: Improved approximation algorithm for two-dimensional bin packing. In: Chekuri, C. (ed.) Proceedings of SODA 2014, pp. 13\u201325. SIAM ( 2014)","DOI":"10.1137\/1.9781611973402.2"},{"issue":"3","key":"1152_CR37","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":"1152_CR38","unstructured":"G\u00e1lvez, W., Grandoni, F., Khan, A., Ramirez-Romero, D., Wiese, A.: Improved approximation algorithms for 2-dimensional knapsack: packing into multiple l-shapes, spirals and more. In: SoCG, pp. 39\u201313917 (2021)"},{"key":"1152_CR39","doi-asserted-by":"crossref","unstructured":"G\u00e1lvez, W., Grandoni, F., Heydrich, S., Ingala, S., Khan, A., Wiese, A.: Approximating geometric knapsack via l-packings. In: FOCS, pp. 260\u2013271 (2017)","DOI":"10.1109\/FOCS.2017.32"},{"key":"1152_CR40","doi-asserted-by":"crossref","unstructured":"Bansal, N., Lodi, A., Sviridenko, M.: A tale of two dimensional bin packing. In: FOCS, pp. 657\u2013666 (2005)","DOI":"10.1109\/SFCS.2005.10"},{"key":"1152_CR41","unstructured":"Khan, A., Pittu, M.R.: On guillotine separability of squares and rectangles. In: APPROX, pp. 47\u201314722 (2020)"},{"key":"1152_CR42","unstructured":"Khan, A., Maiti, A., Sharma, A., Wiese, A.: On guillotine separable packings for the two-dimensional geometric knapsack problem. In: SoCG, pp. 48\u201314817 (2021)"},{"issue":"4","key":"1152_CR43","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/3326122","volume":"66","author":"A Adamaszek","year":"2019","unstructured":"Adamaszek, A., Har-Peled, S., Wiese, A.: Approximation schemes for independent set and sparse subsets of polygons. J. ACM 66(4), 29\u201312940 (2019)","journal-title":"J. ACM"},{"key":"1152_CR44","doi-asserted-by":"crossref","unstructured":"Grandoni, F., M\u00f6mke, T., Wiese, A., Zhou, H.: A (5\/3 + $$\\varepsilon $$)-approximation for unsplittable flow on a path: placing small tasks into boxes. In: STOC, pp. 607\u2013619 (2018)","DOI":"10.1145\/3188745.3188894"},{"key":"1152_CR45","unstructured":"M\u00f6mke, T., Wiese, A.: Breaking the barrier of 2 for the storage allocation problem. In: ICALP, pp. 86\u201318619 ( 2020)"},{"key":"1152_CR46","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."},{"issue":"4","key":"1152_CR47","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). https:\/\/doi.org\/10.1142\/S1793830911001413","journal-title":"Discrete Math. Algorithms Appl."},{"key":"1152_CR48","unstructured":"Rau, M.: Useful structures and how to find them: hardness and approximation results for various variants of the parallel task scheduling problem. dissertation, Kiel University, Kiel (2019)"},{"key":"1152_CR49","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, pp. 312\u2013320. IEEE Computer Society (1982)","DOI":"10.1109\/SFCS.1982.61"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01152-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01152-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01152-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T04:27:38Z","timestamp":1729830458000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01152-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,27]]},"references-count":49,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["1152"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01152-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,27]]},"assertion":[{"value":"31 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Arindam Khan declares that Prof. Susanne Albers was his postdoc mentor and Prof. Joseph Cheriyan was a coauthor. The other authors have no conflict of interest to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}