On the upper bound of the generalization of $\mathsf{FFD}$ to solve $q$BP for some special cases

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\dots$ 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}({\mathsf{D}}_{\mathsf{q}})$ on a carefully chosen subinstance ${D^{\prime }}_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}({\mathsf{D}}_{\mathsf{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.

14 pages; work in progress