File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s10878-015-9976-5
- Scopus: eid_2-s2.0-84950272164
- WOS: WOS:000394241000009
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Online bin packing problem with buffer and bounded size revisited
Title | Online bin packing problem with buffer and bounded size revisited |
---|---|
Authors | |
Keywords | Asymptotic competitive ratio Bin packing Online algorithm |
Issue Date | 2017 |
Publisher | Springer 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? |
Abstract | In 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 Identifier | http://hdl.handle.net/10722/261201 |
ISSN | 2021 Impact Factor: 1.262 2020 SCImago Journal Rankings: 0.538 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Zhang, MH | - |
dc.contributor.author | Han, X | - |
dc.contributor.author | Lan, Y | - |
dc.contributor.author | Ting, HF | - |
dc.date.accessioned | 2018-09-14T08:54:12Z | - |
dc.date.available | 2018-09-14T08:54:12Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | Journal of Combinatorial Optimization, 2017, v. 33 n. 2, p. 530-542 | - |
dc.identifier.issn | 1382-6905 | - |
dc.identifier.uri | http://hdl.handle.net/10722/261201 | - |
dc.description.abstract | In 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.language | eng | - |
dc.publisher | Springer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905 | - |
dc.relation.ispartof | Journal of Combinatorial Optimization | - |
dc.rights | The final publication is available at Springer via http://dx.doi.org/[insert DOI] | - |
dc.subject | Asymptotic competitive ratio | - |
dc.subject | Bin packing | - |
dc.subject | Online algorithm | - |
dc.title | Online bin packing problem with buffer and bounded size revisited | - |
dc.type | Article | - |
dc.identifier.email | Ting, HF: hfting@cs.hku.hk | - |
dc.identifier.authority | Ting, HF=rp00177 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/s10878-015-9976-5 | - |
dc.identifier.scopus | eid_2-s2.0-84950272164 | - |
dc.identifier.hkuros | 290689 | - |
dc.identifier.volume | 33 | - |
dc.identifier.issue | 2 | - |
dc.identifier.spage | 530 | - |
dc.identifier.epage | 542 | - |
dc.identifier.isi | WOS:000394241000009 | - |
dc.publisher.place | Netherlands | - |
dc.identifier.issnl | 1382-6905 | - |