File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing

TitleOnline algorithms for 1-space bounded multi dimensional bin packing and hypercube packing
Authors
Keywords1-space bounded
Bin packing
Multi dimensional
Online algorithms
Issue Date2013
PublisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905
Citation
Journal Of Combinatorial Optimization, 2013, v. 26 n. 2, p. 223-236 How to Cite?
AbstractIn this paper, we study 1-space bounded multi-dimensional bin packing and hypercube packing. A sequence of items arrive over time, each item is a d-dimensional hyperbox (in bin packing) or hypercube (in hypercube packing), and the length of each side is no more than 1. These items must be packed without overlapping into d-dimensional hypercubes with unit length on each side. In d-dimensional space, any two dimensions i and j define a space P ij. When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items, and 90 {ring operator}-rotation on any plane P ij is allowed. The objective is to minimize the total number of bins used for packing all these items in the sequence. In the 1-space bounded variant, there is only one active bin for packing the current item. If the active bin does not have enough space to pack the item, it must be closed and a new active bin is opened. For d-dimensional bin packing, an online algorithm with competitive ratio 4 d is given. Moreover, we consider d-dimensional hypercube packing, and give a 2 d+1-competitive algorithm. These two results are the first study on 1-space bounded multi dimensional bin packing and hypercube packing. © 2012 The Author(s).
Persistent Identifierhttp://hdl.handle.net/10722/147128
ISSN
2015 Impact Factor: 1.08
2015 SCImago Journal Rankings: 1.093
ISI Accession Number ID
References

Bansal N, Correa JR, Kenyon C, Sviridenko M (2006a) Bin packing in multiple dimensions: in-approximability results and approximation schemes. Math Oper Res 31(1):31–49 doi: 10.1287/moor.1050.0168

Chung FRK, Garey MR, Johnson DS (1982) On packing two-dimensional bins. SIAM J Algebr Discrete Methods 3(1):66–76 doi: 10.1137/0603007

Coppersmith D, Raghavan P (1989) Multidimensional on-line bin packing: algorithms and worst case analysis. Oper Res Lett 8:17–20 doi: 10.1016/0167-6377(89)90027-8

Csirik J, Johnson DS (2001) Bounded space on-line bin packing: best is better than first. Algorithmica 31:115–138 doi: 10.1007/s00453-001-0041-7

Csirik J, Frenk J, Labbe M (1993) Two-dimensional rectangle packing: on-line methods and results. Discrete Appl Math 45(3):197–204 doi: 10.1016/0166-218X(93)90009-D

Epstein L, van Stee R (2005a) Online square and cube packing. Acta Inform 41(9):595–606 doi: 10.1007/s00236-005-0169-z

Epstein L, van Stee R (2005b) Optimal online algorithms for multidimensional packing problems. SIAM J Comput 35(2):431–448 doi: 10.1137/S0097539705446895

Epstein L, van Stee R (2007) Bounds for online bounded space hypercube packing. Discrete Optim 4:185–197 doi: 10.1016/j.disopt.2006.11.005

Fujita S (2003) On-line grid-packing with a single active grid. Inf Process Lett 85:199–204 doi: 10.1016/S0020-0190(02)00373-3

Han X, Iwama K, Zhang G (2008) Online removable square packing. Theory Comput Syst 43(1):38–55 doi: 10.1007/s00224-007-9039-0

Han X, Chin F, Ting H-F, Zhang G, Zhang Y (2011) A new upper bound 2.5545 on 2D online bin packing. ACM Trans Algorithms 7(4):50 doi: 10.1145/2000807.2000818

Januszewski J, Lassak M (1997) On-line packing sequences of cubes in the unit cube. Geom Dedic 67:285–293 doi: 10.1023/A:1004953109743

Johnson DS, Garey MR (1985) A 71/60 theorem for bin-packing. J Complex 1:65–106 doi: 10.1016/0885-064X(85)90022-6

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–325 doi: 10.1137/0203025

Kohayakawa Y, Miyazawa FK, Raghavan P, Wakabayashi Y (2004) Multidimensionalcube packing. Algorithmica 40(3):173–187 doi: 10.1007/s00453-004-1102-5

Lee CC, Lee DT (1985) A simple on-line bin packing algorithm. J Assoc Comput Mach 32:562–572 doi: 10.1145/3828.3833

Leung JY-T, Tam TW, Wong CS, Young GH, Chin FYL (1990) Packing squares into a square. J Parallel Distrib Comput 10:271–275 doi: 10.1016/0743-7315(90)90019-L

Meir A, Moser L (1968) On packing of squares and cubes. J Comb Theory 5:126–134 doi: 10.1016/S0021-9800(68)80047-X

Ramanan PV, Brown DJ, Lee CC, Lee DT (1989) On-line bin packing in linear time. J Algorithms 10:305–326 doi: 10.1016/0196-6774(89)90031-X

Seiden SS (2002) On the online bin packing problem. J ACM 49:640–671 doi: 10.1145/585265.585269

Seiden S, van Stee R (2003) New bounds for multi-dimensional packing. Algorithmica 36:261–293 doi: 10.1007/s00453-003-1016-7

Simchi-Levi D (1994) New worst-case results for the bin-packing problem. Nav Res Logist 41:579–585 doi: 10.1002/1520-6750(199406)41:4%3C579::AID-NAV3220410409%3E3.0.CO;2-G

van Vliet A (1992) An improved lower bound for on-line bin packing algorithms. Inf Process Lett 43:277–284 doi: 10.1016/0020-0190(92)90223-I

Yao AC-C (1980) New algorithms for bin packing. J ACM 27:207–227 doi: 10.1145/322186.322187

 

DC FieldValueLanguage
dc.contributor.authorZhang, Yen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorHan, Xen_HK
dc.date.accessioned2012-05-28T08:19:43Z-
dc.date.available2012-05-28T08:19:43Z-
dc.date.issued2013en_HK
dc.identifier.citationJournal Of Combinatorial Optimization, 2013, v. 26 n. 2, p. 223-236en_HK
dc.identifier.issn1382-6905en_HK
dc.identifier.urihttp://hdl.handle.net/10722/147128-
dc.description.abstractIn this paper, we study 1-space bounded multi-dimensional bin packing and hypercube packing. A sequence of items arrive over time, each item is a d-dimensional hyperbox (in bin packing) or hypercube (in hypercube packing), and the length of each side is no more than 1. These items must be packed without overlapping into d-dimensional hypercubes with unit length on each side. In d-dimensional space, any two dimensions i and j define a space P ij. When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items, and 90 {ring operator}-rotation on any plane P ij is allowed. The objective is to minimize the total number of bins used for packing all these items in the sequence. In the 1-space bounded variant, there is only one active bin for packing the current item. If the active bin does not have enough space to pack the item, it must be closed and a new active bin is opened. For d-dimensional bin packing, an online algorithm with competitive ratio 4 d is given. Moreover, we consider d-dimensional hypercube packing, and give a 2 d+1-competitive algorithm. These two results are the first study on 1-space bounded multi dimensional bin packing and hypercube packing. © 2012 The Author(s).en_HK
dc.languageengen_US
dc.publisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905en_HK
dc.relation.ispartofJournal of Combinatorial Optimizationen_HK
dc.rightsThe Author(s)en_US
dc.rightsCreative Commons: Attribution 3.0 Hong Kong Licenseen_US
dc.subject1-space boundeden_HK
dc.subjectBin packingen_HK
dc.subjectMulti dimensionalen_HK
dc.subjectOnline algorithmsen_HK
dc.titleOnline algorithms for 1-space bounded multi dimensional bin packing and hypercube packingen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://www.springerlink.com/link-out/?id=2104&code=02757VP772851072&MUD=MPen_US
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturepublished_or_final_versionen_US
dc.identifier.doi10.1007/s10878-012-9457-zen_HK
dc.identifier.scopuseid_2-s2.0-84879883028en_HK
dc.identifier.hkuros208020-
dc.identifier.hkuros215789-
dc.relation.referencesBansal N, Correa JR, Kenyon C, Sviridenko M (2006a) Bin packing in multiple dimensions: in-approximability results and approximation schemes. Math Oper Res 31(1):31–49en_US
dc.relation.referencesdoi: 10.1287/moor.1050.0168en_US
dc.relation.referencesChung FRK, Garey MR, Johnson DS (1982) On packing two-dimensional bins. SIAM J Algebr Discrete Methods 3(1):66–76en_US
dc.relation.referencesdoi: 10.1137/0603007en_US
dc.relation.referencesCoppersmith D, Raghavan P (1989) Multidimensional on-line bin packing: algorithms and worst case analysis. Oper Res Lett 8:17–20en_US
dc.relation.referencesdoi: 10.1016/0167-6377(89)90027-8en_US
dc.relation.referencesCsirik J, Johnson DS (2001) Bounded space on-line bin packing: best is better than first. Algorithmica 31:115–138en_US
dc.relation.referencesdoi: 10.1007/s00453-001-0041-7en_US
dc.relation.referencesCsirik J, Frenk J, Labbe M (1993) Two-dimensional rectangle packing: on-line methods and results. Discrete Appl Math 45(3):197–204en_US
dc.relation.referencesdoi: 10.1016/0166-218X(93)90009-Den_US
dc.relation.referencesEpstein L, van Stee R (2005a) Online square and cube packing. Acta Inform 41(9):595–606en_US
dc.relation.referencesdoi: 10.1007/s00236-005-0169-zen_US
dc.relation.referencesEpstein L, van Stee R (2005b) Optimal online algorithms for multidimensional packing problems. SIAM J Comput 35(2):431–448en_US
dc.relation.referencesdoi: 10.1137/S0097539705446895en_US
dc.relation.referencesEpstein L, van Stee R (2007) Bounds for online bounded space hypercube packing. Discrete Optim 4:185–197en_US
dc.relation.referencesdoi: 10.1016/j.disopt.2006.11.005en_US
dc.relation.referencesFujita S (2003) On-line grid-packing with a single active grid. Inf Process Lett 85:199–204en_US
dc.relation.referencesdoi: 10.1016/S0020-0190(02)00373-3en_US
dc.relation.referencesHan X, Iwama K, Zhang G (2008) Online removable square packing. Theory Comput Syst 43(1):38–55en_US
dc.relation.referencesdoi: 10.1007/s00224-007-9039-0en_US
dc.relation.referencesHan X, Chin F, Ting H-F, Zhang G, Zhang Y (2011) A new upper bound 2.5545 on 2D online bin packing. ACM Trans Algorithms 7(4):50en_US
dc.relation.referencesdoi: 10.1145/2000807.2000818en_US
dc.relation.referencesJanuszewski J, Lassak M (1997) On-line packing sequences of cubes in the unit cube. Geom Dedic 67:285–293en_US
dc.relation.referencesdoi: 10.1023/A:1004953109743en_US
dc.relation.referencesJohnson DS, Garey MR (1985) A 71/60 theorem for bin-packing. J Complex 1:65–106en_US
dc.relation.referencesdoi: 10.1016/0885-064X(85)90022-6en_US
dc.relation.referencesJohnson 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–325en_US
dc.relation.referencesdoi: 10.1137/0203025en_US
dc.relation.referencesKohayakawa Y, Miyazawa FK, Raghavan P, Wakabayashi Y (2004) Multidimensionalcube packing. Algorithmica 40(3):173–187en_US
dc.relation.referencesdoi: 10.1007/s00453-004-1102-5en_US
dc.relation.referencesLee CC, Lee DT (1985) A simple on-line bin packing algorithm. J Assoc Comput Mach 32:562–572en_US
dc.relation.referencesdoi: 10.1145/3828.3833en_US
dc.relation.referencesLeung JY-T, Tam TW, Wong CS, Young GH, Chin FYL (1990) Packing squares into a square. J Parallel Distrib Comput 10:271–275en_US
dc.relation.referencesdoi: 10.1016/0743-7315(90)90019-Len_US
dc.relation.referencesMeir A, Moser L (1968) On packing of squares and cubes. J Comb Theory 5:126–134en_US
dc.relation.referencesdoi: 10.1016/S0021-9800(68)80047-Xen_US
dc.relation.referencesRamanan PV, Brown DJ, Lee CC, Lee DT (1989) On-line bin packing in linear time. J Algorithms 10:305–326en_US
dc.relation.referencesdoi: 10.1016/0196-6774(89)90031-Xen_US
dc.relation.referencesSeiden SS (2002) On the online bin packing problem. J ACM 49:640–671en_US
dc.relation.referencesdoi: 10.1145/585265.585269en_US
dc.relation.referencesSeiden S, van Stee R (2003) New bounds for multi-dimensional packing. Algorithmica 36:261–293en_US
dc.relation.referencesdoi: 10.1007/s00453-003-1016-7en_US
dc.relation.referencesSimchi-Levi D (1994) New worst-case results for the bin-packing problem. Nav Res Logist 41:579–585en_US
dc.relation.referencesdoi: 10.1002/1520-6750(199406)41:4%3C579::AID-NAV3220410409%3E3.0.CO;2-Gen_US
dc.relation.referencesvan Vliet A (1992) An improved lower bound for on-line bin packing algorithms. Inf Process Lett 43:277–284en_US
dc.relation.referencesdoi: 10.1016/0020-0190(92)90223-Ien_US
dc.relation.referencesYao AC-C (1980) New algorithms for bin packing. J ACM 27:207–227en_US
dc.relation.referencesdoi: 10.1145/322186.322187en_US
dc.relation.referencesBansal N, Caprara A, Sviridenko M (2006b) Improved approximation algorithm for multidimensional bin packing problems. In: FOCS 2006, pp 697–708en_US
dc.relation.referencesBlitz D, van Vliet A, Woeginger GJ (1996) Lower bounds on the asymptotic worst-case ratio of on-line bin packing algorithms. Unpublished manuscripten_US
dc.relation.referencesCaprara A (2002) Packing 2-dimensional bins in harmony. In FOCS 2002, pp 490–499en_US
dc.relation.referencesChin FYL, Ting H-F, Zhang Y (2012) 1-space bounded algorithms for 2-dimensional bin packing. Int J Found Comput Sci (to appear)en_US
dc.relation.referencesFerreira CE, Miyazawa EK, Wakabayashi Y (1999) Packing squares into squares. Pesqui Oper 19:223–237en_US
dc.relation.referencesGarey MR, Johnson DS (1979) Computers and intractability: a guide for the theory of NP-completeness. Freeman, San Franciscoen_US
dc.relation.referencesHan X, Fujita S, Guo H (2001) A two-dimensional harmonic algorithm with performance ratio 2.7834. IPSJ SIG Not 93:43–50en_US
dc.relation.referencesKarmarkar N, 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–320en_US
dc.relation.referencesZhang Y, Chen J, Chin FYL, Han X, 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–253en_US
dc.identifier.spage223en_HK
dc.identifier.epage236en_HK
dc.identifier.eissn1573-2886en_US
dc.identifier.isiWOS:000321062500001-
dc.publisher.placeNetherlandsen_HK
dc.description.otherSpringer Open Choice, 28 May 2012en_US
dc.identifier.scopusauthoridZhang, Y=35114314500en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridHan, X=34872071800en_HK
dc.identifier.citeulike10385009-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats