File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A new upper bound 2.5545 on 2D online bin packing

TitleA new upper bound 2.5545 on 2D online bin packing
Authors
KeywordsBin packing problems
Competitive ratio
Online algorithms
Asymptotic competitive ratio
Bin packing
Issue Date2011
PublisherAssociation for Computing Machinery, Inc.
Citation
ACM Transactions on Algorithms, 2011, v. 7 n. 4, article no. 50 How to Cite?
AbstractThe 2D Online Bin Packing is a fundamental problem in Computer Science and the determination of its asymptotic competitive ratio has research attention. In a long series of papers, the lower bound of this ratio has been improved from 1.808, 1.856 to 1.907 and its upper bound reduced from 3.25, 3.0625, 2.8596, 2.7834 to 2.66013. In this article, we rewrite the upper bound record to 2.5545. Our idea for the improvement is as follows. In 2002, Seiden and van Stee [Seiden and van Stee 2003] proposed an elegant algorithm called H. C, comprised of the Harmonic algorithm H and the Improved Harmonic algorithm C, for the two-dimensional online bin packing problem and proved that the algorithm has an asymptotic competitive ratio of at most 2.66013. Since the best known online algorithm for one-dimensional bin packing is the Super Harmonic algorithm [Seiden 2002], a natural question to ask is: could a better upper bound be achieved by using the Super Harmonic algorithm instead of the Improved Harmonic algorithm? However, as mentioned in Seiden and van Stee [2003], the previous analysis framework does not work. In this article, we give a positive answer for this question. A new upper bound of 2.5545 is obtained for 2-dimensional online bin packing. The main idea is to develop new weighting functions for the Super Harmonic algorithm and propose new techniques to bound the total weight in a rectangular bin. © 2011 ACM.
Persistent Identifierhttp://hdl.handle.net/10722/152469
ISSN
2015 Impact Factor: 0.776
2015 SCImago Journal Rankings: 1.796
ISI Accession Number ID
Funding AgencyGrant Number
Fundamental Research Funds for the Central Universities
NFSC11101065
NSFC10971192
Funding Information:

X. Han was partially supported by the Fundamental Research Funds for the Central Universities and NFSC (11101065). G. Zhang was partially supported by NSFC (10971192).

References

 

DC FieldValueLanguage
dc.contributor.authorHan, Xen_US
dc.contributor.authorHan, Xen_US
dc.contributor.authorChin, FYLen_US
dc.contributor.authorTing, HFen_US
dc.contributor.authorZhang, GCen_US
dc.contributor.authorZhang, Y-
dc.date.accessioned2012-06-26T06:39:27Z-
dc.date.available2012-06-26T06:39:27Z-
dc.date.issued2011en_US
dc.identifier.citationACM Transactions on Algorithms, 2011, v. 7 n. 4, article no. 50en_US
dc.identifier.issn1549-6325en_US
dc.identifier.urihttp://hdl.handle.net/10722/152469-
dc.description.abstractThe 2D Online Bin Packing is a fundamental problem in Computer Science and the determination of its asymptotic competitive ratio has research attention. In a long series of papers, the lower bound of this ratio has been improved from 1.808, 1.856 to 1.907 and its upper bound reduced from 3.25, 3.0625, 2.8596, 2.7834 to 2.66013. In this article, we rewrite the upper bound record to 2.5545. Our idea for the improvement is as follows. In 2002, Seiden and van Stee [Seiden and van Stee 2003] proposed an elegant algorithm called H. C, comprised of the Harmonic algorithm H and the Improved Harmonic algorithm C, for the two-dimensional online bin packing problem and proved that the algorithm has an asymptotic competitive ratio of at most 2.66013. Since the best known online algorithm for one-dimensional bin packing is the Super Harmonic algorithm [Seiden 2002], a natural question to ask is: could a better upper bound be achieved by using the Super Harmonic algorithm instead of the Improved Harmonic algorithm? However, as mentioned in Seiden and van Stee [2003], the previous analysis framework does not work. In this article, we give a positive answer for this question. A new upper bound of 2.5545 is obtained for 2-dimensional online bin packing. The main idea is to develop new weighting functions for the Super Harmonic algorithm and propose new techniques to bound the total weight in a rectangular bin. © 2011 ACM.en_US
dc.languageengen_US
dc.publisherAssociation for Computing Machinery, Inc.-
dc.relation.ispartofACM Transactions on Algorithmsen_US
dc.rightsACM Transactions on Algorithms. Copyright © Association for Computing Machinery, Inc.-
dc.subjectBin packing problemsen_US
dc.subjectCompetitive ratioen_US
dc.subjectOnline algorithmsen_US
dc.subjectAsymptotic competitive ratio-
dc.subjectBin packing-
dc.titleA new upper bound 2.5545 on 2D online bin packingen_US
dc.typeArticleen_US
dc.identifier.emailChin, FYL: chin@cs.hku.hken_US
dc.identifier.emailTing, HF: hfting@cs.hku.hken_US
dc.identifier.emailZhang, Y: yongzh@hkucc.hku.hk-
dc.identifier.authorityChin, FYL=rp00105en_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.description.naturelink_to_OA_fulltexten_US
dc.identifier.doi10.1145/2000807.2000818en_US
dc.identifier.scopuseid_2-s2.0-80053540909en_US
dc.identifier.hkuros208030-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-80053540909&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume7en_US
dc.identifier.issue4en_US
dc.identifier.eissn1549-6333-
dc.identifier.isiWOS:000296200900011-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridZhang, Y=35114314500en_US
dc.identifier.scopusauthoridZhang, G=7405271610en_US
dc.identifier.scopusauthoridTing, HF=7005654198en_US
dc.identifier.scopusauthoridChin, FYL=7005101915en_US
dc.identifier.scopusauthoridHan, X=34872071800en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats