File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Online bin packing problem with buffer and bounded size revisited

TitleOnline bin packing problem with buffer and bounded size revisited
Authors
KeywordsAsymptotic competitive ratio
Bin packing
Online algorithm
Issue Date2017
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, 2017, v. 33 n. 2, p. 530-542 How to Cite?
AbstractIn this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within (α, 1 / 2 ] where 0 ≤ α< 1 / 2 , and there is a buffer with constant size. Each time when a new item is given, it can be stored in the buffer temporarily or packed into some bin, once it is packed in the bin, we cannot repack it. If the input is ended, the items in the buffer should be packed into bins too. In our setting, any time there is at most one bin open, i.e., that bin can accept new items, and all the other bins are closed. This problem is first studied by Zheng et al. (J Combin Optim 30(2):360–369, 2015), and they proposed a 1.4444-competitive algorithm and a lower bound 1.3333 on the competitive ratio. We improve the lower bound from 1.3333 to 1.4230, and the upper bound from 1.4444 to 1.4243.
Persistent Identifierhttp://hdl.handle.net/10722/261201
ISSN
2017 Impact Factor: 0.927
2015 SCImago Journal Rankings: 1.093

 

DC FieldValueLanguage
dc.contributor.authorZhang, MH-
dc.contributor.authorHan, X-
dc.contributor.authorLan, Y-
dc.contributor.authorTing, HF-
dc.date.accessioned2018-09-14T08:54:12Z-
dc.date.available2018-09-14T08:54:12Z-
dc.date.issued2017-
dc.identifier.citationJournal of Combinatorial Optimization, 2017, v. 33 n. 2, p. 530-542-
dc.identifier.issn1382-6905-
dc.identifier.urihttp://hdl.handle.net/10722/261201-
dc.description.abstractIn this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within (α, 1 / 2 ] where 0 ≤ α< 1 / 2 , and there is a buffer with constant size. Each time when a new item is given, it can be stored in the buffer temporarily or packed into some bin, once it is packed in the bin, we cannot repack it. If the input is ended, the items in the buffer should be packed into bins too. In our setting, any time there is at most one bin open, i.e., that bin can accept new items, and all the other bins are closed. This problem is first studied by Zheng et al. (J Combin Optim 30(2):360–369, 2015), and they proposed a 1.4444-competitive algorithm and a lower bound 1.3333 on the competitive ratio. We improve the lower bound from 1.3333 to 1.4230, and the upper bound from 1.4444 to 1.4243.-
dc.languageeng-
dc.publisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905-
dc.relation.ispartofJournal of Combinatorial Optimization-
dc.rightsThe final publication is available at Springer via http://dx.doi.org/[insert DOI]-
dc.subjectAsymptotic competitive ratio-
dc.subjectBin packing-
dc.subjectOnline algorithm-
dc.titleOnline bin packing problem with buffer and bounded size revisited-
dc.typeArticle-
dc.identifier.emailTing, HF: hfting@cs.hku.hk-
dc.identifier.authorityTing, HF=rp00177-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/s10878-015-9976-5-
dc.identifier.scopuseid_2-s2.0-84950272164-
dc.identifier.hkuros290689-
dc.identifier.volume33-
dc.identifier.issue2-
dc.identifier.spage530-
dc.identifier.epage542-
dc.publisher.placeNetherlands-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats