We continue the study of bin packing with splittable items and cardinality constraints. In this problem, a set of n items must be packed into as few bins as possible. Items may be split, but each bin may contain at most k (parts of) items, where k is some given parameter. Complicating the problem further is the fact that items may be larger than 1, which is the size of a bin. The problem is known to be strongly NP‐hard for any fixed value of k. We essentially close this problem by providing an efficient polynomial‐time approximation scheme (EPTAS) for most of its versions. Namely, we present an efficient polynomial time approximation scheme for k=o(n). A PTAS for k=Θ(n) does not exist unless P = NP. Additionally, we present dual approximation schemes for k=2 and for constant values of k. Thus we show that for any ϵ>0, it is possible to pack the items into the optimal number of bins in polynomial time, if the algorithm may use bins of size 1+ϵ.
