{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:39:32Z","timestamp":1787341172765,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>In the three-dimensional (3D) strip packing problem, we are given a set of 3D rectangular items and a 3D box $B$. The goal is to pack all the items in $B$ such that the height of the packing is minimized. We consider the most basic version of the problem, where the items must be packed with their edges parallel to the edges of $B$ and cannot be rotated. Building upon Caprara's work for the two-dimensional (2D) bin packing problem, we obtain an algorithm that, given any $\\epsilon&gt;0$, achieves an approximation of $T_{\\infty}+\\epsilon\\approx1.69103+\\epsilon$, where $T_{\\infty}$ is the well-known number that occurs naturally in the context of bin packing. Our key idea is to establish a connection between bin packing solutions for an arbitrary instance $I$ and the strip packing solutions for the corresponding instance obtained from $I$ by applying the harmonic transformation to certain dimensions. Based on this connection, we also give a simple alternate proof of the $T_{\\infty}+\\epsilon$ approximation for 2D bin packing due to Caprara. In particular, we show how his result follows from a simple modification of the asymptotic approximation scheme for 2D strip packing due to Kenyon and R\u00e9mila.<\/jats:p>","DOI":"10.1137\/070691607","type":"journal-article","created":{"date-parts":[[2013,3,28]],"date-time":"2013-03-28T10:33:13Z","timestamp":1364466793000},"page":"579-592","source":"Crossref","is-referenced-by-count":11,"title":["A Harmonic Algorithm for the 3D Strip Packing Problem"],"prefix":"10.1137","volume":"42","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Han","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kazuo","family":"Iwama","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maxim","family":"Sviridenko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guochuan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,3,28]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/0209064"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"N. Bansal, A. Caprara, and M. Sviridenko,\n                      Improved approximation algorithms for multidimensional bin packing problems\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 697-708.","DOI":"10.1109\/FOCS.2006.38"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/080736831"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0168"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"A. Caprara,\n                      Packing two-dimensional bins in harmony\n                      , in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 490-499.","DOI":"10.1109\/SFCS.2002.1181973"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1070.0289"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/0209062"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2005.02.005"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579456"},{"key":"atypb10","first-page":"358","author":"Han X.","year":"2007","journal-title":"Berlin"},{"key":"atypb11","unstructured":"D. S. Johnson,\n                      Near-Optimal Bin Packing Algorithms\n                      , Doctoral thesis, MIT, Cambridge, MA, 1973."},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"K. Jansen and R. Solis-Oba,\n                      An asymptotic approximation algorithm for 3D-strip packing\n                      , in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 143-152.","DOI":"10.1145\/1109557.1109575"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"N. Karmarkar and R. M. Karp,\n                      An efficient approximation scheme for the one-dimensional bin-packing problem\n                      , in Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982, pp. 312-320.","DOI":"10.1109\/SFCS.1982.61"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.4.645.12118"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/0219059"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90058-K"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3833"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(68)80047-X"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523692"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1287\/moor.20.2.257"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070691607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:08:35Z","timestamp":1787339315000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070691607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/070691607"],"URL":"https:\/\/doi.org\/10.1137\/070691607","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}