The multiple subset sum problem

In the multiple subset sum problem (MSSP) items from a given ground set are selected and packed into a given number of identical bins such that the su m of the item weights in every bin does not exceed the bin capacity and the total sum of the weights of the items packed is as large as possible. This problem is a relevant special case of the multiple knapsack problem, f or which the existence of a polynomial-time approximation scheme (PTAS) is an important open question in the field of knapsack problems. One main resu lt of the present paper is the construction of a PTAS for MSSP. For the bottleneck case of the problem, where the minimum total weight cont ained in any bin is to be maximized, we describe a 2/3-approximation algori thm and show that this is the best possible approximation ratio. Moreover, PTASs are derived for the special cases in which either the number of bins or the number of different item weights is constant. We finally show that, even for the case of only two bins, no fully PTAS exi sts for both versions of the problem.