Bin packing with hierarchical item types

Abstract We consider the following version of online bin packing. Arriving items of rational sizes in (0, 1] belong to a constant number of types denoted by $$1,2,\ldots ,k$$ 1 , 2 , … , k , and there are unbounded numbers of available bins of these types. The cost of a bin depends on its type, and the sequence of costs is monotonically increasing. Every item of type i can be packed into a bin of type whose index is at least i , and no bin may have a total size of items that is larger than 1. Items are presented one by one to be packed into suitable bins, where the information regarding bin types is known in advance. The cost of the algorithm is the total cost of used bins, and the goal is to minimize the cost. We show tight bounds on the absolute competitive ratio for the case of three types ( $$k=3$$ k = 3 ), and tight bounds for the overall bound with an arbitrary number of types k , where those bounds are 2 and 4 for $$k=3$$ k = 3 and for arbitrary k , respectively.