A polynomial time approximation scheme for the multiple knapsack problem

The multiple knapsack problem (MKP) is a natural and well-known generalization of the single knapsack problem and is defined as follows. We are given a set of n items and m bins ( knapsacks) such that each item i has a profit p( i) and a size s( i), and each bin j has a capacity c( j). The goal is to find a subset of items of maximum profit such that they have a feasible packing in the bins. MKP is a special case of the generalized assignment problem ( GAP) where the profit and the size of an item can vary based on the specific bin that it is assigned to. GAP is APX-hard and a 2-approximation, for it is implicit in the work of Shmoys and Tardos [ Math. Program. A, 62 ( 1993), pp. 461 - 474], and thus far, this was also the best known approximation for MKP. The main result of this paper is a polynomial time approximation scheme (PTAS) for MKP. Apart from its inherent theoretical interest as a common generalization of the well-studied knapsack and bin packing problems, it appears to be the strongest special case of GAP that is not APX-hard. We substantiate this by showing that slight generalizations of MKP are APX-hard. Thus our results help demarcate the boundary at which instances of GAP become APX-hard. An interesting aspect of our approach is a PTAS-preserving reduction from an arbitrary instance of MKP to an instance with O(log n) distinct sizes and profits.