{"ID":6536202,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10731","arxiv_id":"2607.10731","title":"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\\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.","short_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$....","url_abs":"https://arxiv.org/abs/2607.10731","url_pdf":"https://arxiv.org/pdf/2607.10731v1","authors":"[\"Dinesh Kumar Baghel\"]","published":"2026-07-12T12:30:06Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}