{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,26]],"date-time":"2024-01-26T11:23:00Z","timestamp":1706268180910},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2013,8]]},"DOI":"10.1007\/s10878-012-9457-z","type":"journal-article","created":{"date-parts":[[2012,2,16]],"date-time":"2012-02-16T16:13:02Z","timestamp":1329408782000},"page":"223-236","source":"Crossref","is-referenced-by-count":7,"title":["Online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing"],"prefix":"10.1007","volume":"26","author":[{"given":"Yong","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francis Y. L.","family":"Chin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hing-Fung","family":"Ting","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xin","family":"Han","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"issue":"1","key":"9457_CR1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1287\/moor.1050.0168","volume":"31","author":"N Bansal","year":"2006","unstructured":"Bansal\u00a0N, Correa JR, Kenyon\u00a0C, Sviridenko\u00a0M (2006a) Bin packing in multiple dimensions: in-approximability results and approximation schemes. Math Oper Res 31(1):31\u201349","journal-title":"Math Oper Res"},{"key":"9457_CR2","first-page":"697","volume-title":"FOCS 2006","author":"N Bansal","year":"2006","unstructured":"Bansal\u00a0N, Caprara\u00a0A, Sviridenko\u00a0M (2006b) Improved approximation algorithm for multidimensional bin packing problems. In: FOCS 2006, pp\u00a0697\u2013708"},{"key":"9457_CR3","doi-asserted-by":"crossref","unstructured":"Blitz\u00a0D, van Vliet\u00a0A, Woeginger GJ (1996) Lower bounds on the asymptotic worst-case ratio of on-line bin packing algorithms. Unpublished manuscript","DOI":"10.1006\/jagm.1996.0005"},{"key":"9457_CR4","first-page":"490","volume-title":"FOCS 2002","author":"A Caprara","year":"2002","unstructured":"Caprara\u00a0A (2002) Packing 2-dimensional bins in harmony. In FOCS 2002, pp\u00a0490\u2013499"},{"key":"9457_CR5","unstructured":"Chin FYL, Ting H-F, Zhang\u00a0Y (2012) 1-space bounded algorithms for 2-dimensional bin packing. Int J Found Comput Sci (to appear)"},{"issue":"1","key":"9457_CR6","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1137\/0603007","volume":"3","author":"FRK Chung","year":"1982","unstructured":"Chung FRK, Garey MR, Johnson DS (1982) On packing two-dimensional bins. SIAM J Algebr Discrete Methods 3(1):66\u201376","journal-title":"SIAM J Algebr Discrete Methods"},{"key":"9457_CR7","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0167-6377(89)90027-8","volume":"8","author":"D Coppersmith","year":"1989","unstructured":"Coppersmith\u00a0D, Raghavan\u00a0P (1989) Multidimensional on-line bin packing: algorithms and worst case analysis. Oper Res Lett 8:17\u201320","journal-title":"Oper Res Lett"},{"key":"9457_CR8","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s00453-001-0041-7","volume":"31","author":"J Csirik","year":"2001","unstructured":"Csirik\u00a0J, Johnson DS (2001) Bounded space on-line bin packing: best is better than first. Algorithmica 31:115\u2013138","journal-title":"Algorithmica"},{"issue":"3","key":"9457_CR9","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0166-218X(93)90009-D","volume":"45","author":"J Csirik","year":"1993","unstructured":"Csirik\u00a0J, Frenk\u00a0J, Labbe\u00a0M (1993) Two-dimensional rectangle packing: on-line methods and results. Discrete Appl Math 45(3):197\u2013204","journal-title":"Discrete Appl Math"},{"issue":"9","key":"9457_CR10","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1007\/s00236-005-0169-z","volume":"41","author":"L Epstein","year":"2005","unstructured":"Epstein\u00a0L, van\u00a0Stee\u00a0R (2005a) Online square and cube packing. Acta Inform 41(9):595\u2013606","journal-title":"Acta Inform"},{"issue":"2","key":"9457_CR11","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/S0097539705446895","volume":"35","author":"L Epstein","year":"2005","unstructured":"Epstein\u00a0L, van Stee\u00a0R (2005b) Optimal online algorithms for multidimensional packing problems. SIAM J Comput 35(2):431\u2013448","journal-title":"SIAM J Comput"},{"key":"9457_CR12","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/j.disopt.2006.11.005","volume":"4","author":"L Epstein","year":"2007","unstructured":"Epstein\u00a0L, van Stee\u00a0R (2007) Bounds for online bounded space hypercube packing. Discrete Optim 4:185\u2013197","journal-title":"Discrete Optim"},{"key":"9457_CR13","first-page":"223","volume":"19","author":"CE Ferreira","year":"1999","unstructured":"Ferreira CE, Miyazawa EK, Wakabayashi\u00a0Y (1999) Packing squares into squares. Pesqui Oper 19:223\u2013237","journal-title":"Pesqui Oper"},{"key":"9457_CR14","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0020-0190(02)00373-3","volume":"85","author":"S Fujita","year":"2003","unstructured":"Fujita\u00a0S (2003) On-line grid-packing with a single active grid. Inf Process Lett 85:199\u2013204","journal-title":"Inf Process Lett"},{"key":"9457_CR15","volume-title":"Computers and intractability: a\u00a0guide for the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a\u00a0guide for the theory of NP-completeness. Freeman, San Francisco"},{"key":"9457_CR16","first-page":"43","volume":"93","author":"X Han","year":"2001","unstructured":"Han\u00a0X, Fujita\u00a0S, Guo\u00a0H (2001) A\u00a0two-dimensional harmonic algorithm with performance ratio 2.7834. IPSJ SIG Not 93:43\u201350","journal-title":"IPSJ SIG Not"},{"issue":"1","key":"9457_CR17","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/s00224-007-9039-0","volume":"43","author":"X Han","year":"2008","unstructured":"Han\u00a0X, Iwama\u00a0K, Zhang\u00a0G (2008) Online removable square packing. Theory Comput Syst 43(1):38\u201355","journal-title":"Theory Comput Syst"},{"issue":"4","key":"9457_CR18","first-page":"50","volume":"7","author":"X Han","year":"2011","unstructured":"Han\u00a0X, Chin\u00a0F, Ting H-F, Zhang\u00a0G, Zhang\u00a0Y (2011) A\u00a0new upper bound 2.5545 on 2D online bin packing. ACM Trans Algorithms 7(4):50","journal-title":"ACM Trans Algorithms"},{"key":"9457_CR19","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1023\/A:1004953109743","volume":"67","author":"J Januszewski","year":"1997","unstructured":"Januszewski\u00a0J, Lassak\u00a0M (1997) On-line packing sequences of cubes in the unit cube. Geom Dedic 67:285\u2013293","journal-title":"Geom Dedic"},{"key":"9457_CR20","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0885-064X(85)90022-6","volume":"1","author":"DS Johnson","year":"1985","unstructured":"Johnson DS, Garey MR (1985) A\u00a071\/60 theorem for bin-packing. J Complex 1:65\u2013106","journal-title":"J Complex"},{"issue":"4","key":"9457_CR21","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson DS, Demers AJ, Ullman JD, Garey MR, Graham RL (1974) Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J Comput 3(4):299\u2013325","journal-title":"SIAM J Comput"},{"key":"9457_CR22","first-page":"312","volume-title":"Proc 23rd ann IEEE symp on foundations of comput sci","author":"N Karmarkar","year":"1982","unstructured":"Karmarkar\u00a0N, Karp RM (1982) An efficient approximation scheme for the one-dimensional bin packing problem. In: Proc 23rd ann IEEE symp on foundations of comput sci. IEEE Computer Society, Los Alamitos, pp 312\u2013320"},{"issue":"3","key":"9457_CR23","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s00453-004-1102-5","volume":"40","author":"Y Kohayakawa","year":"2004","unstructured":"Kohayakawa\u00a0Y, Miyazawa FK, Raghavan\u00a0P, Wakabayashi\u00a0Y (2004) Multidimensionalcube packing. Algorithmica 40(3):173\u2013187","journal-title":"Algorithmica"},{"key":"9457_CR24","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"CC Lee","year":"1985","unstructured":"Lee CC, Lee DT (1985) A\u00a0simple on-line bin packing algorithm. J Assoc Comput Mach 32:562\u2013572","journal-title":"J Assoc Comput Mach"},{"key":"9457_CR25","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0743-7315(90)90019-L","volume":"10","author":"JY-T Leung","year":"1990","unstructured":"Leung JY-T, Tam TW, Wong CS, Young GH, Chin FYL (1990) Packing squares into a square. J Parallel Distrib Comput 10:271\u2013275","journal-title":"J Parallel Distrib Comput"},{"key":"9457_CR26","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/S0021-9800(68)80047-X","volume":"5","author":"A Meir","year":"1968","unstructured":"Meir\u00a0A, Moser\u00a0L (1968) On packing of squares and cubes. J Comb Theory 5:126\u2013134","journal-title":"J Comb Theory"},{"key":"9457_CR27","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0196-6774(89)90031-X","volume":"10","author":"PV Ramanan","year":"1989","unstructured":"Ramanan PV, Brown DJ, Lee CC, Lee DT (1989) On-line bin packing in linear time. J Algorithms 10:305\u2013326","journal-title":"J Algorithms"},{"key":"9457_CR28","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1145\/585265.585269","volume":"49","author":"SS Seiden","year":"2002","unstructured":"Seiden SS (2002) On the online bin packing problem. J ACM 49:640\u2013671","journal-title":"J ACM"},{"key":"9457_CR29","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/s00453-003-1016-7","volume":"36","author":"S Seiden","year":"2003","unstructured":"Seiden\u00a0S, van Stee\u00a0R (2003) New bounds for multi-dimensional packing. Algorithmica 36:261\u2013293","journal-title":"Algorithmica"},{"key":"9457_CR30","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1002\/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G","volume":"41","author":"D Simchi-Levi","year":"1994","unstructured":"Simchi-Levi\u00a0D (1994) New worst-case results for the bin-packing problem. Nav Res Logist 41:579\u2013585","journal-title":"Nav Res Logist"},{"key":"9457_CR31","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\u00a0A (1992) An improved lower bound for on-line bin packing algorithms. Inf Process Lett 43:277\u2013284","journal-title":"Inf Process Lett"},{"key":"9457_CR32","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1145\/322186.322187","volume":"27","author":"AC-C Yao","year":"1980","unstructured":"Yao AC-C (1980) New algorithms for bin packing. J ACM 27:207\u2013227","journal-title":"J ACM"},{"key":"9457_CR33","series-title":"LNCS","first-page":"242","volume-title":"Proc of the 21th annual international symposium on algorithms and computation (ISAAC 2010)","author":"Y Zhang","year":"2010","unstructured":"Zhang\u00a0Y, Chen\u00a0J, Chin FYL, Han\u00a0X, Ting H-F, Tsin YH (2010) Improved online algorithms for 1-space bounded 2-dimensional bin packing. In: Proc of the 21th annual international symposium on algorithms and computation (ISAAC 2010). LNCS, vol 6507. Springer, Berlin, pp 242\u2013253"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9457-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T20:44:19Z","timestamp":1561322659000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-012-9457-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,17]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["9457"],"URL":"https:\/\/doi.org\/10.1007\/s10878-012-9457-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,17]]}}}