Indexed by:Journal Papers

Date of Publication:2015-08-01

Journal:JOURNAL OF COMBINATORIAL OPTIMIZATION

Included Journals:Scopus、EI、SCIE

Volume:30

Issue:2,SI

Page Number:276-298

ISSN:1382-6905

Key Words:Bin packing; Competitive ratio; Linear programming

Abstract:We study a variant of online bin packing problem, in which there are two types of bins: and , i.e., unit size bin with cost 1 and size 2 bin with cost , the objective is to minimize the total cost occurred when all the items are packed into the two types of bins. When , the offline version of this problem is equivalent to the classical bin packing problem. In this paper, we focus on the case , and propose online algorithms and obtain lower bounds for the problem.