File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Improved online algorithms for 1-space bounded 2-dimensional bin packing

TitleImproved online algorithms for 1-space bounded 2-dimensional bin packing
Authors
KeywordsBin packing problem
Competitive ratio
Lower bounds
On-line algorithms
Packing algorithms
Issue Date2010
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju Island, Korea, 15-17 December 2010. In Lecture Notes in Computer Science, 2010, v. 6507, pt. 2, p. 242-253 How to Cite?
AbstractIn this paper, we study 1-space bounded 2-dimensional bin packing and square packing. A sequence of rectangular items (square items, respectively) arrive over time, which must be packed into square bins of size 1×1. 90°-rotation of an item is allowed. When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items. The objective is to minimize the total number of bins used for packing all the 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. Our contributions are as follows: For 1-space bounded 2-dimensional bin packing, we propose an online packing strategy with competitive ratio 5.155, surpassing the previous 8.84-competitive bound. The lower bound of competitive ratio is also improved from 2.5 to 3. Furthermore, we study 1-space bounded square packing, which is a special case of the bin packing problem. We give a 4.5-competitive packing algorithm, and prove that the lower bound of competitive ratio is at least 8/3. © 2010 Springer-Verlag.
Persistent Identifierhttp://hdl.handle.net/10722/125685
ISBN
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorZhang, Yen_HK
dc.contributor.authorChen, Jen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorHan, Xen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorTsin, YHen_HK
dc.date.accessioned2010-10-31T11:45:58Z-
dc.date.available2010-10-31T11:45:58Z-
dc.date.issued2010en_HK
dc.identifier.citationThe 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju Island, Korea, 15-17 December 2010. In Lecture Notes in Computer Science, 2010, v. 6507, pt. 2, p. 242-253en_HK
dc.identifier.isbn9783642175138 (pt. 2)-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/125685-
dc.description.abstractIn this paper, we study 1-space bounded 2-dimensional bin packing and square packing. A sequence of rectangular items (square items, respectively) arrive over time, which must be packed into square bins of size 1×1. 90°-rotation of an item is allowed. When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items. The objective is to minimize the total number of bins used for packing all the 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. Our contributions are as follows: For 1-space bounded 2-dimensional bin packing, we propose an online packing strategy with competitive ratio 5.155, surpassing the previous 8.84-competitive bound. The lower bound of competitive ratio is also improved from 2.5 to 3. Furthermore, we study 1-space bounded square packing, which is a special case of the bin packing problem. We give a 4.5-competitive packing algorithm, and prove that the lower bound of competitive ratio is at least 8/3. © 2010 Springer-Verlag.-
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Science-
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectBin packing problem-
dc.subjectCompetitive ratio-
dc.subjectLower bounds-
dc.subjectOn-line algorithms-
dc.subjectPacking algorithms-
dc.titleImproved online algorithms for 1-space bounded 2-dimensional bin packingen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailZhang, Y: yzhang@cs.hku.hken_HK
dc.identifier.emailChen, J: jchen@cs.hku.hken_HK
dc.identifier.emailChin, FYL: chin@cs.hku.hken_HK
dc.identifier.emailHan, X: hanxin.mail@gmail.com-
dc.identifier.emailTing, HF: hfting@cs.hku.hk-
dc.identifier.emailTsin, YH: peter@uwindsor.ca-
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-17514-5_21-
dc.identifier.scopuseid_2-s2.0-78650878708-
dc.identifier.hkuros178828en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-78650878708&selection=ref&src=s&origin=recordpage-
dc.identifier.volume6507-
dc.identifier.issuept. 2-
dc.identifier.spage242-
dc.identifier.epage253-
dc.publisher.placeGermany-
dc.description.otherThe 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju Island, Korea, 15-17 December 2010. In Lecture Notes in Computer Science, 2010, v. 6507, pt. 2, p. 242-253-
dc.identifier.scopusauthoridZhang, Y=35114314500-
dc.identifier.scopusauthoridChen, J=36719773300-
dc.identifier.scopusauthoridChin, FYL=7005101915-
dc.identifier.scopusauthoridHan, X=34872071800-
dc.identifier.scopusauthoridTing, HF=7005654198-
dc.identifier.scopusauthoridTsin, YH=6603741679-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats