{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T14:55:42Z","timestamp":1776696942004,"version":"3.51.2"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,9,1]],"date-time":"2011-09-01T00:00:00Z","timestamp":1314835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11101065"],"award-info":[{"award-number":["11101065"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["10971192"],"award-info":[{"award-number":["10971192"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:p>The 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.<\/jats:p>\n          <jats:p>\n            In 2002, Seiden and van Stee [Seiden and van Stee 2003] proposed an elegant algorithm called\n            <jats:italic>H<\/jats:italic>\n            \u2297\n            <jats:italic>C<\/jats:italic>\n            , comprised of the\n            <jats:italic>Harmonic algorithm<\/jats:italic>\n            <jats:italic>H<\/jats:italic>\n            and the\n            <jats:italic>Improved Harmonic algorithm<\/jats:italic>\n            <jats:italic>C<\/jats:italic>\n            , 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\n            <jats:italic>Super Harmonic algorithm<\/jats:italic>\n            [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.\n          <\/jats:p>","DOI":"10.1145\/2000807.2000818","type":"journal-article","created":{"date-parts":[[2011,9,27]],"date-time":"2011-09-27T14:02:19Z","timestamp":1317132139000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["A new upper bound 2.5545 on 2D Online Bin Packing"],"prefix":"10.1145","volume":"7","author":[{"given":"Xin","family":"Han","sequence":"first","affiliation":[{"name":"Dalian University of Technology, Dalian, P.R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francis Y. L.","family":"Chin","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hing-Fung","family":"Ting","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guochuan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Zhejiang University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,9,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/080736831"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0168"},{"key":"e_1_2_1_3_1","unstructured":"Blitz D. van Vliet A. and Woeginger G. J. 1996. Lower bounds on the asymptotic worst-case ratio of online bin packing alorithms. Unpublished manuscript.  Blitz D. van Vliet A. and Woeginger G. J. 1996. Lower bounds on the asymptotic worst-case ratio of online bin packing alorithms. Unpublished manuscript."},{"key":"e_1_2_1_4_1","unstructured":"Brown D. 1979. A lower bound for on-line one-dimensional bin packing algorithms. Tech. rep. R864 Coordinated Science Lab. Urbana Illinois.  Brown D. 1979. A lower bound for on-line one-dimensional bin packing algorithms. Tech. rep. R864 Coordinated Science Lab. Urbana Illinois."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652191"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0603007"},{"key":"e_1_2_1_7_1","unstructured":"Coffman E. Garey M. and Johnson D. 1987. Approximation Algorithms for Bin Packing: A Survey chapter 2. PWS Boston MA.  Coffman E. Garey M. and Johnson D. 1987. Approximation Algorithms for Bin Packing: A Survey chapter 2. PWS Boston MA."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90027-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90009-D"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(93)90004-Z"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'04)","author":"Epstein L."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-005-0169-z"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446895"},{"key":"e_1_2_1_14_1","first-page":"1","article-title":"A 1.6 lower-bound for the two-dimensional on-line rectange bin-packing","volume":"10","author":"Galambos G.","year":"1991","journal-title":"Acta Cybern."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02246509"},{"key":"e_1_2_1_16_1","unstructured":"GLP. http:\/\/www.gnu.org\/software\/glpk.  GLP. http:\/\/www.gnu.org\/software\/glpk."},{"key":"e_1_2_1_17_1","first-page":"43","article-title":"A two-dimensional harmonic algorithm with performance ratio 2.7834","volume":"93","author":"Han X.","year":"2001","journal-title":"IPSJ SIG Notes"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11970125_18"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203025"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3833"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(80)90077-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00647-3"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90031-X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585269"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1016-7"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90223-I"},{"key":"e_1_2_1_27_1","unstructured":"van Vliet A. 1995. Lower and upper bounds for online bin packing and scheduling heuristics. Ph.D. dissertation. Erasmus University.  van Vliet A. 1995. Lower and upper bounds for online bin packing and scheduling heuristics. Ph.D. dissertation. Erasmus University."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322187"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2000807.2000818","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2000807.2000818","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:00:03Z","timestamp":1750244403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2000807.2000818"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["10.1145\/2000807.2000818"],"URL":"https:\/\/doi.org\/10.1145\/2000807.2000818","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9]]},"assertion":[{"value":"2008-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}