{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T14:10:17Z","timestamp":1718979017191},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,11,16]],"date-time":"2012-11-16T00:00:00Z","timestamp":1353024000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,4]]},"DOI":"10.1007\/s00453-012-9713-8","type":"journal-article","created":{"date-parts":[[2012,11,15]],"date-time":"2012-11-15T17:14:34Z","timestamp":1352999674000},"page":"1019-1044","source":"Crossref","is-referenced-by-count":5,"title":["Online Square Packing with Gravity"],"prefix":"10.1007","volume":"68","author":[{"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[]},{"given":"Tom","family":"Kamphans","sequence":"additional","affiliation":[]},{"given":"Nils","family":"Schweer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,11,16]]},"reference":[{"issue":"2","key":"9713_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"},{"issue":"3","key":"9713_CR2","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1137\/0212033","volume":"12","author":"B.S. Baker","year":"1983","unstructured":"Baker, B.S., Schwarz, J.S.: Shelf algorithms for two-dimensional packing problems. SIAM J. Comput. 12(3), 508\u2013525 (1983)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9713_CR3","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1137\/0209064","volume":"9","author":"B.S. 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)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9713_CR4","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1016\/0196-6774(81)90034-1","volume":"2","author":"B.S. 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"},{"key":"9713_CR5","series-title":"Lect. Notes Comput. Sci.","first-page":"25","volume-title":"Proc. 8th Internat. Workshop Approx. Online Algor","author":"J. Balogh","year":"2010","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. In: Proc. 8th Internat. Workshop Approx. Online Algor. Lect. Notes Comput. Sci., vol. 6534, pp.\u00a025\u201336 (2010)"},{"issue":"1\u20132","key":"9713_CR6","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1142\/S0218195904001354","volume":"14","author":"R. Breukelaar","year":"2004","unstructured":"Breukelaar, R., Demaine, E.D., Hohenberger, S., Hoogeboom, H.J., Kosters, W.A., Liben-Nowell, D.: Tetris is hard, even to approximate. Int. J. Comput. Geom. Appl. 14(1\u20132), 41\u201368 (2004)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"2","key":"9713_CR7","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BF00264439","volume":"18","author":"D.J. Brown","year":"1982","unstructured":"Brown, D.J., Baker, B.S., Katseff, H.P.: Lower bounds for on-line two-dimensional packing algorithms. Acta Inform. 18(2), 207\u2013225 (1982)","journal-title":"Acta Inform."},{"key":"9713_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24804-0","volume-title":"Scheduling Algorithms","author":"P. Brucker","year":"2004","unstructured":"Brucker, P.: Scheduling Algorithms, 2nd edn. Springer, Berlin (2004)","edition":"2"},{"issue":"4","key":"9713_CR9","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"E.G. 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)","journal-title":"SIAM J. Comput."},{"issue":"10","key":"9713_CR10","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1007\/s00236-002-0089-0","volume":"38","author":"E.G. Coffman Jr.","year":"2002","unstructured":"Coffman, E.G. Jr., Downey, P.J., Winkler, P.: Packing rectangles in a strip. Acta Inform. 38(10), 673\u2013693 (2002)","journal-title":"Acta Inform."},{"issue":"4","key":"9713_CR11","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/S0020-0190(97)00120-8","volume":"63","author":"J. Csirik","year":"1997","unstructured":"Csirik, J., Woeginger, G.J.: Shelf algorithms for on-line strip packing. Inf. Process. Lett. 63(4), 171\u2013175 (1997)","journal-title":"Inf. Process. Lett."},{"key":"9713_CR12","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, 595\u2013606 (2005)","journal-title":"Acta Inform."},{"key":"9713_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/3-540-69346-7_20","volume-title":"Proceedings of the 6th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201998)","author":"S.P. Fekete","year":"1998","unstructured":"Fekete, S.P., Schepers, J.: New classes of lower bounds for bin packing problems. In: Proceedings of the 6th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201998). Lecture Notes in Computer Science, vol. 1412, pp. 257\u2013270. Springer, Berlin (1998)"},{"key":"9713_CR14","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1287\/opre.1060.0369","volume":"55","author":"S.P. Fekete","year":"2007","unstructured":"Fekete, S.P., Schepers, J., van der Veen, J.: An exact algorithm for higher-dimensional orthogonal packing. Oper. Res. 55, 569\u2013587 (2007)","journal-title":"Oper. Res."},{"key":"9713_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/978-3-642-03367-4_27","volume-title":"Proceedings of the 11th Algorithms and Data Structures Symposium (WADS\u201909)","author":"S.P. Fekete","year":"2009","unstructured":"Fekete, S.P., Kamphans, T., Schweer, N.: Online square packing. In: Proceedings of the 11th Algorithms and Data Structures Symposium (WADS\u201909). Lecture Notes in Computer Science, vol. 5664, pp. 302\u2013314. Springer, Berlin (2009)"},{"issue":"2","key":"9713_CR16","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0166-218X(93)90037-O","volume":"41","author":"G. Galambos","year":"1993","unstructured":"Galambos, G., Frenk, J.B.G.: A simple proof of Liang\u2019s lower bound for online bin packing and the extension to the parametric case. Discrete Appl. Math. 41(2), 173\u2013178 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9713_CR17","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF01415672","volume":"42","author":"G. Galambos","year":"1995","unstructured":"Galambos, G., Woeginger, G.J.: Online bin packing\u2014a restricted survey. Math. Methods Oper. Res. 42(1), 25\u201345 (1995)","journal-title":"Math. Methods Oper. Res."},{"issue":"2","key":"9713_CR18","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R.L. Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"9713_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1007\/978-3-540-72870-2_34","volume-title":"Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM\u201907)","author":"X. Han","year":"2007","unstructured":"Han, X., Iwama, K., Ye, D., Zhang, G.: Strip packing vs. bin packing. In: Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM\u201907). Lecture Notes in Computer Science, vol. 4508, pp. 358\u2013367. Springer, Berlin (2007)"},{"key":"9713_CR20","first-page":"31","volume-title":"Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, (FOCS\u201996)","author":"C. Kenyon","year":"1996","unstructured":"Kenyon, C., R\u00e9mila, E.: Approximate strip packing. In: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, (FOCS\u201996), pp. 31\u201336. IEEE Comput. Soc., Los Alamitos (1996)"},{"key":"9713_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/BFb0049416","volume-title":"Proceedings of the 2nd Annual European Symposium on Algorithms (ESA\u201994)","author":"I. Schiermeyer","year":"1994","unstructured":"Schiermeyer, I.: Reverse-fit: A 2-optimal algorithm for packing rectangles. In: Proceedings of the 2nd Annual European Symposium on Algorithms (ESA\u201994). Lecture Notes in Computer Science, vol. 855, pp. 290\u2013299. Springer, Berlin (1994)"},{"issue":"5","key":"9713_CR22","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1145\/585265.585269","volume":"49","author":"S.S. Seiden","year":"2002","unstructured":"Seiden, S.S.: On the online bin packing problem. J. ACM 49(5), 640\u2013671 (2002)","journal-title":"J. ACM"},{"issue":"1","key":"9713_CR23","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(80)90121-0","volume":"10","author":"D.D. 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)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9713_CR24","doi-asserted-by":"crossref","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."},{"issue":"5","key":"9713_CR25","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0020-0190(92)90223-I","volume":"43","author":"A. Vliet van","year":"1992","unstructured":"van Vliet, A.: An improved lower bound for online bin packing algorithms. Inf. Process. Lett. 43(5), 277\u2013284 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9713_CR26","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s10878-007-9125-x","volume":"17","author":"D. Ye","year":"2009","unstructured":"Ye, D., Han, X., Zhang, G.: A note on online strip packing. J. Comb. Optim. 17(4), 417\u2013423 (2009)","journal-title":"J. Comb. Optim."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9713-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9713-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9713-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:10Z","timestamp":1559123110000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9713-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,16]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["9713"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9713-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,11,16]]}}}