Polynomial time approximation schemes for class-constrained packing problems (Q1348737)

The paper considers generalizations of the classical bin packing and multiple knapsack problems. It is assumed that every item is given a size and a class (a colour). In the class-constrained bin packing (CCBP) problem it is required to minimize the number of bins of the unit size that can be used to pack all items, provided that a bin contains items of no more than a prescribed number of colours. In the class-constrained multiple-knapsack (CCMK) problem each item additionally is given a value (profit), the total number of bins of various sizes is given and it is required to maximize total value of items placed in the bins, provided that the size constraints and the colour constraints are respected. Problem CCMK is shown to admit a polynomial-time approximation scheme (PTAS) that finds a placement with a value at least \((1-\varepsilon)\) times the optimum. Further, problem CCMK with a single bin admits a fully polynomial-time approximation scheme. For problem CCBP a dual PTAS is developed that allows a placement into the optimal number of bins provided that the bin size is extended to \(1-\varepsilon\). On the other hand, if an item can take any colour of a given set of colours, the resulting generalized packing problem becomes APX-hard even in the case of a single bin, equal sizes and equal values of all items.