Online bin packing with (1,1) and (2,) bins

摘要

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.