Indexed by:期刊论文

Date of Publication:2017-02-01

Journal:JOURNAL OF COMBINATORIAL OPTIMIZATION

Included Journals:SCIE、EI

Volume:33

Issue:2

Page Number:530-542

ISSN No.:1382-6905

Key Words:Bin packing; Online algorithm; Asymptotic competitive ratio

Abstract:In this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within where , 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.