Item

Abstract

We continue the study of bin packing with splittable items and cardinality constraints. In this problem, a set of 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 fixed constant. Complicating the problem further is the fact that items may be larger than 1, which is the size of a bin. We close this problem by providing a polynomial-time approximation scheme for it. We first present a scheme for the case $k=2$ and then for the general case of constant $k$. Additionally, we present \emph{dual} approximation schemes for $k=2$ and constant $k$. Thus we show that for any $\varepsilon>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+\varepsilon$.