AI summaryⓘ
The authors study a version of the bin packing problem where multiple copies of items must be packed, with the restriction that no bin contains more than one copy of the same item and bin capacity cannot be exceeded. They focus on how a common algorithm called First Fit Decreasing (FFD) works in this situation and address a challenge since usual assumptions about how FFD packs items do not apply here. By analyzing a special subset of the input, they prove that the generalized FFD algorithm has an approximation ratio bounded by (11/9) times the optimal number of bins plus an additional term that depends on the number of copies. This gives an understanding of how well FFD performs on this more complex packing problem.
Bin packing problemFirst Fit Decreasing (FFD)Approximation ratioItem copies constraintBin capacityAlgorithm analysisPacking optimizationMultiplicitiesCombinatorial optimization
Abstract
We consider a variant of the bin packing problem with constraints on the number of copies of each item and their placement in the packing. The input $D_q := DD\ldots$ is defined as $q$ consecutive copies of the multiset $D$, with a fixed bin capacity $S$. Note that, for each item in $D$, there are $q$ copies in $D_q$. The goal is to pack all the items in $D_q$ into the minimum number of bins, such that each bin contains at most one copy of each item and the total size of all items in a bin does not exceed the bin capacity $S$. We call this problem $q$BP. First Fit Decreasing ($\mathsf{FFD}$) is a classical bin packing algorithm: it first orders the items in nonincreasing order, then packs the next item into the first bin where it fits. In the literature, $\mathsf{FFD}$ proofs rely on the assumption that the last bin in the $\mathsf{FFD}$ packing contains only a single item. This assumption does not naturally extend to the $q$BP problem. In this paper, we circumvent this difficulty by analyzing $\mathsf{FFDq(D_q)}$ on a carefully chosen subinstance ${D'}_q \subseteq D_q$ ($q$ consecutive copies of $D$, each copy sorted in non-increasing order) while preserving the same upper bound for the original input $D_q$. We show that the approximation ratio of $\mathsf{FFDq(D_q)}$ for some special cases is \begin{align*} \mathsf{FFDq(D_q)} \leq \frac{11}{9}\mathsf{OPT(D_q)} + 3q \end{align*} where $\mathsf{FFDq}$ and $\mathsf{OPT}$ denote the number of bins used by the $\mathsf{FFD}$ generalization and by an optimal algorithm, respectively.