{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:44Z","timestamp":1740109244840,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,1,11]],"date-time":"2016-01-11T00:00:00Z","timestamp":1452470400000},"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":["FE407\/17-1"],"award-info":[{"award-number":["FE407\/17-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s00453-016-0114-2","type":"journal-article","created":{"date-parts":[[2016,1,11]],"date-time":"2016-01-11T09:39:37Z","timestamp":1452505177000},"page":"867-901","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Online Square-into-Square Packing"],"prefix":"10.1007","volume":"77","author":[{"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hella-Franziska","family":"Hoffmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,11]]},"reference":[{"issue":"2","key":"114_CR1","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1006\/jagm.1997.0876","volume":"25","author":"Y Azar","year":"1997","unstructured":"Azar, Y., Epstein, L.: On two dimensional packing. J. Algorithms 25(2), 290\u2013310 (1997)","journal-title":"J. Algorithms"},{"key":"114_CR2","doi-asserted-by":"crossref","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, pp. 77\u201386 (2009)","DOI":"10.1007\/978-3-642-10631-6_10"},{"key":"114_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Caprara, A., Sviridenko, M.: Improved approximation algorithms for multidimensional bin packing problems. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 697\u2013708 (2006)","DOI":"10.1109\/FOCS.2006.38"},{"issue":"4","key":"114_CR4","doi-asserted-by":"crossref","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)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"114_CR5","doi-asserted-by":"crossref","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":"2","key":"114_CR6","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1137\/070691607","volume":"42","author":"N Bansal","year":"2013","unstructured":"Bansal, N., Han, X., Iwama, K., Sviridenko, M., Zhang, G.: A harmonic algorithm for the 3D strip packing problem. SIAM J. Comput. 42(2), 579\u2013592 (2013)","journal-title":"SIAM J. Comput."},{"key":"114_CR7","doi-asserted-by":"crossref","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 (2014)","DOI":"10.1137\/1.9781611973402.2"},{"key":"114_CR8","doi-asserted-by":"crossref","unstructured":"Bansal, N., Lodi, A., Sviridenko, M.: A tale of two dimensional bin packing. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 657\u2013666 (2005)","DOI":"10.1109\/SFCS.2005.10"},{"key":"114_CR9","unstructured":"Bansal, N., Sviridenko, M.: New approximability and inapproximability results for 2-dimensional bin packing. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 196\u2013203 (2004)"},{"key":"114_CR10","doi-asserted-by":"crossref","unstructured":"Caprara, A.: Packing 2-dimensional bins in harmony. In: 43rd Symposium on Foundations of Computer Science (FOCS), pp. 490\u2013499 (2002)","DOI":"10.1109\/SFCS.2002.1181973"},{"issue":"1","key":"114_CR11","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1287\/moor.1070.0289","volume":"33","author":"A Caprara","year":"2008","unstructured":"Caprara, A.: Packing d-dimensional bins in d stages. Math. Oper. Res. 33(1), 203\u2013215 (2008)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"114_CR12","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/j.disopt.2006.06.001","volume":"3","author":"A Caprara","year":"2006","unstructured":"Caprara, A., Lodi, A., Martello, S., Monaci, M.: Packing into the smallest square: worst-case analysis of lower bounds. Discrete Optim. 3(4), 317\u2013326 (2006)","journal-title":"Discrete Optim."},{"issue":"1","key":"114_CR13","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1287\/moor.1040.0112","volume":"30","author":"A Caprara","year":"2005","unstructured":"Caprara, A., Lodi, A., Monaci, M.: Fast approximation schemes for two-stage, two-dimensional bin packing. Math. Oper. Res. 30(1), 150\u2013172 (2005)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"114_CR14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.orl.2005.02.005","volume":"34","author":"JR Correa","year":"2006","unstructured":"Correa, J.R.: Resource augmentation in two-dimensional packing with orthogonal rotations. Oper. Res. Lett. 34(1), 85\u201393 (2006)","journal-title":"Oper. Res. Lett."},{"key":"114_CR15","unstructured":"Correa, J.R., Kenyon, C.: Approximation schemes for multidimensional packing. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2004, pp. 186\u2013195 (2004)"},{"key":"114_CR16","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Fekete, S.P., Lang, R.J.: Circle packing for origami design is hard. In: Origami 5, pp. 609\u2013626. AK Peters\/CRC Press (2011)","DOI":"10.1201\/b10971-52"},{"key":"114_CR17","unstructured":"Epstein, L., van Stee, R.: Optimal online bounded space multidimensional packing. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11\u201314, 2004, pp. 214\u2013223 (2004)"},{"issue":"9","key":"114_CR18","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1007\/s00236-005-0169-z","volume":"41","author":"L Epstein","year":"2005","unstructured":"Epstein, L., van Stee, R.: Online square and cube packing. Acta Inform. 41(9), 595\u2013606 (2005)","journal-title":"Acta Inform."},{"issue":"2","key":"114_CR19","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/j.disopt.2006.11.005","volume":"4","author":"L Epstein","year":"2007","unstructured":"Epstein, L., van Stee, R.: Bounds for online bounded space hypercube packing. Discrete Optim. 4(2), 185\u2013197 (2007)","journal-title":"Discrete Optim."},{"key":"114_CR20","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Hoffmann, H.F.: Online square-into-square packing. In: 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems Proceedings (APPROX), LNCS, vol. 8096, pp. 126\u2013141 (2013)","DOI":"10.1007\/978-3-642-40328-6_10"},{"key":"114_CR21","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Kamphans, T., Schweer, N.: Online square packing. In: 11th International Symposium on Algorithms and Data Structures (WADS), LNCS, vol. 5664, pp. 302\u2013314. Springer, Berlin, Heidelberg (2009)","DOI":"10.1007\/978-3-642-03367-4_27"},{"key":"114_CR22","doi-asserted-by":"crossref","first-page":"1019","DOI":"10.1007\/s00453-012-9713-8","volume":"68","author":"SP Fekete","year":"2014","unstructured":"Fekete, S.P., Kamphans, T., Schweer, N.: Online square packing with gravity. Algorithmica 68, 1019\u20131044 (2014)","journal-title":"Algorithmica"},{"key":"114_CR23","doi-asserted-by":"crossref","unstructured":"Fishkin, A.V., Gerber, O., Jansen, K., Solis-Oba, R.: Packing weighted rectangles into a square. In: Mathematical Foundations of Computer Science, International Symposium (MFCS), LNCS, vol. 3618, pp. 352\u2013363 (2005)","DOI":"10.1007\/11549345_31"},{"issue":"1","key":"114_CR24","first-page":"1","volume":"3","author":"AV Fishkin","year":"2008","unstructured":"Fishkin, A.V., Gerber, O., Jansen, K., Solis-Oba, R.: On packing rectangles with resource augmentation: maximizing the profit. Algorithmic Oper. Res. 3(1), 1\u201312 (2008)","journal-title":"Algorithmic Oper. Res."},{"issue":"1","key":"114_CR25","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/s00224-007-9039-0","volume":"43","author":"X Han","year":"2008","unstructured":"Han, X., Iwama, K., Zhang, G.: Online removable square packing. Theory Comput. Syst. 43(1), 38\u201355 (2008)","journal-title":"Theory Comput. Syst."},{"issue":"44","key":"114_CR26","doi-asserted-by":"crossref","first-page":"4504","DOI":"10.1016\/j.tcs.2009.07.030","volume":"410","author":"R Harren","year":"2009","unstructured":"Harren, R.: Approximation algorithms for orthogonal packing problems for hypercubes. Theor. Comput. Sci. 410(44), 4504\u20134532 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"114_CR27","unstructured":"Harren, R.: Two-dimensional packing problems. Ph.D. thesis, Saarland University (2010)"},{"issue":"8","key":"114_CR28","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1142\/S0129054113500354","volume":"24","author":"R Harren","year":"2013","unstructured":"Harren, R., Jansen, K., Pr\u00e4del, L., Schwarz, U.M., van Stee, R.: Two for one: tight approximation of 2d bin packing. Int. J. Found. Comput. Sci. 24(8), 1299\u20131328 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"114_CR29","doi-asserted-by":"crossref","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 )$$ ( 5 \/ 3 + \u03f5 ) -approximation for strip packing. Comput. Geom. 47(2), 248\u2013267 (2014)","journal-title":"Comput. Geom."},{"issue":"8","key":"114_CR30","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/j.comgeo.2011.05.001","volume":"44","author":"S Hougardy","year":"2011","unstructured":"Hougardy, S.: On packing squares into a rectangle. Comput. Geom. Theory Appl. 44(8), 456\u2013463 (2011)","journal-title":"Comput. Geom. Theory Appl."},{"key":"114_CR31","doi-asserted-by":"crossref","unstructured":"Jansen, K., Pr\u00e4del, L.: New approximability results for two-dimensional bin packing. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pp. 919\u2013936 (2013)","DOI":"10.1137\/1.9781611973105.66"},{"key":"114_CR32","doi-asserted-by":"crossref","unstructured":"Jansen, K., Solis-Oba, R.: New approximability results for 2-dimensional packing problems. In: Mathematical Foundations of Computer Science, International Symposium (MFCS), LNCS, vol. 4708, pp. 103\u2013114 (2007)","DOI":"10.1007\/978-3-540-74456-6_11"},{"key":"114_CR33","doi-asserted-by":"crossref","unstructured":"Jansen, K., Solis-Oba, R.: A polynomial time approximation scheme for the square packing problem. In: Integer Programming and Combinatorial Optimization, 13th International Conference (IPCO), pp. 184\u2013198 (2008)","DOI":"10.1007\/978-3-540-68891-4_13"},{"issue":"3","key":"114_CR34","doi-asserted-by":"crossref","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":"114_CR35","doi-asserted-by":"crossref","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 (2005)","DOI":"10.1145\/1060590.1060702"},{"issue":"3","key":"114_CR36","doi-asserted-by":"crossref","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)","journal-title":"Algorithmica"},{"issue":"3","key":"114_CR37","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1023\/A:1004953109743","volume":"67","author":"J Januszewski","year":"1997","unstructured":"Januszewski, J., Lassak, M.: On-line packing sequences of cubes in the unit cube. Geom. Dedic. 67(3), 285\u2013293 (1997)","journal-title":"Geom. Dedic."},{"key":"114_CR38","doi-asserted-by":"crossref","unstructured":"Kenyon, C., R\u00e9mila, E.: Approximate strip packing. In: 37th Annual Symposium on Foundations of Computer Science (FOCS), pp. 31\u201336 (1996)","DOI":"10.1109\/SFCS.1996.548461"},{"key":"114_CR39","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1111\/j.1749-6632.1970.tb56476.x","volume":"175","author":"D Kleitman","year":"1970","unstructured":"Kleitman, D., Krieger, M.: Packing squares in rectangles I. Ann. N. Y. Acad. Sci. 175, 253\u2013262 (1970)","journal-title":"Ann. N. Y. Acad. Sci."},{"key":"114_CR40","doi-asserted-by":"crossref","unstructured":"Kleitman, D.J., Krieger, M.M.: An optimal bound for two dimensional bin packing. In: 16th Annual Symposium on Foundations of Computer Science (FOCS), pp. 163\u2013168 (1975)","DOI":"10.1109\/SFCS.1975.6"},{"issue":"3","key":"114_CR41","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0743-7315(90)90019-L","volume":"10","author":"JYT Leung","year":"1990","unstructured":"Leung, J.Y.T., 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)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"2","key":"114_CR42","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/S0021-9800(68)80047-X","volume":"5","author":"A Meir","year":"1968","unstructured":"Meir, A., Moser, L.: On packing of squares and cubes. J. Comb. Theory 5(2), 126\u2013134 (1968)","journal-title":"J. Comb. Theory"},{"key":"114_CR43","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4064\/cm-17-1-103-110","volume":"17","author":"J Moon","year":"1967","unstructured":"Moon, J., Moser, L.: Some packing and covering theorems. Colloq. Math. 17, 103\u2013110 (1967)","journal-title":"Colloq. Math."},{"key":"114_CR44","unstructured":"Moser, L.: Poorly formulated unsolved problems of combinatorial geometry. Mimeographed (1966)"},{"key":"114_CR45","first-page":"35","volume":"10","author":"P Novotn\u00fd","year":"1995","unstructured":"Novotn\u00fd, P.: A note on a packing of squares. Stud. Univ. Transp. Commun. Ilina Math. Phys. Ser. 10, 35\u201339 (1995)","journal-title":"Stud. Univ. Transp. Commun. Ilina Math. Phys. Ser."},{"issue":"2","key":"114_CR46","first-page":"75","volume":"32","author":"P Novotn\u00fd","year":"1996","unstructured":"Novotn\u00fd, P.: On packing of squares into a rectangle. Arch. Math. (Brno) 32(2), 75\u201383 (1996)","journal-title":"Arch. Math. (Brno)"},{"key":"114_CR47","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Chen, J.C., Chin, F.Y.L., Han, X., Ting, H.F., Tsin, Y.H.: Improved online algorithms for 1-space bounded 2-dimensional bin packing. In: 21st International Symposium on Algorithms and Computation (ISAAC), LNCS, vol. 6507, pp. 242\u2013253 (2010)","DOI":"10.1007\/978-3-642-17514-5_21"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0114-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0114-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0114-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0114-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,3]],"date-time":"2019-09-03T07:24:20Z","timestamp":1567495460000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0114-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,11]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["114"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0114-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,1,11]]}}}