A NOTE ON DUAL APPROXIMATION ALGORITHMS FOR CLASS CONSTRAINED BIN PACKING PROBLEMS

In this paper we present a dual approximation scheme forthe class constrained shelf bin packing problem. In this problem, weare given bins of capacity 1, andn items of Q different classes, eachitem e with classce and size s e . The problem is to pack the items intobins, such that two items of different classes packed in a same bin mustbe in different shelves. Items in a same shelf are packed consecutively.Moreover, items in consecutive shelves must be separated by shelf divi-sors of size d . In a shelf bin packing problem, we have to obtain a shelfpacking such that the total size of items and shelf divisors in any binis at most 1. A dual approximation scheme must obtain a shelf pack-ing of all items into N bins, such that, the total size of all items andshelf divisors packed in any bin is at most 1 + ε for a given ε> 0andN is the number of bins used in an optimum shelf bin packing prob-lem. Shelf divisors are used to avoid contact between items of differentclasses and can hold a set of items until a maximum given weight. Wealso present a dual approximation scheme for the class constrained binpacking problem. In this problem, there is no use of shelf divisors, buteach bin uses at most C different classes