On the Upper Bound of the Generalization of FFD to Solve qBP for Some Special Cases

Jul 16, 2026

Upload by Rowan

A variant of the bin packing problem, q-times bin packing (qBP), is studied under constraints that each item can appear at most once per bin while appearing in q different bins across the packing. The input Dq consists of q consecutive copies of a multiset D, with items ordered by a fixed bin capacity S. A generalized First Fit Decreasing algorithm (FFDq) is analyzed to bound its number of bins versus an optimal solution for selected special cases.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages14

Reading Time35 min

Introduction

Literature Review

Definitions and Notations

FFDq Upper Bound For Special Cases

Conclusion

arXiv :2607 . 1073 1v 1 [ cs .DS] 12 Jul 2026 On the upper bound of the generalization of FFD to solve qBP for some special cases Working Paper Dinesh Kumar Baghel School of Computer Science, UPES, Dehradun-248007 [dinkubag21@gmail. com](dinkubag21@gmail. com) July 14, 2026 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 Dq := DD . . . 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 Dq . The goal is to pack all the items in Dq 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 qBP. First Fit Decreasing (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, FFD proofs rely on the assumption that the last bin in the FFD packing contains only a single item. This assumption does not naturally extend to the qBP problem. In this paper, we circumvent this difficulty by analyzing FFDq on a carefully chosen subinstance D′ q ⊆ Dq (q consecutive copies of D, each copy sorted in non-increasing order) while preserving the same upper bound for the original input Dq . We show that the approximation ratio of FFDq for some special cases is 11 FFDq (Dq) ≤ OPT (Dq ) + 3q 9 where FFDq and OPT denote the number of bins used by the FFD generalization and by an optimal algorithm, respectively. Contents 1 Introduction 2 2 Literature Review 3 3 Definitions and Notations 3 4 FFDq Upper Bound For Special Cases 4 5 Conclusion 13 1 Introduction We define q-times bin packing (or qBP in short) as: given a multiset of items of different sizes, a fixed bin capacity, and an integer q ≥ 1. The qBP problem is to pack these items into a minimum number of bins such that the sum of the sizes of the items in a bin does not exceed the bin capacity. The packing mustsatify the following constraints: C1 : each item appears at most once in a bin, and C2 : each item appears in q different bins. We call these constraints as qBP constraints. Formally, we consider a (multi)set D of positive real numbers, a positive number S that represents the bin capacity S, and an integer q ≥ 1. Typically, P di > S (where di is the size of item i in D) . Given q, the goal is to pack the items in D in a minimum number of bins such that the packing satisifies the qBP constraints. The problem qBP has application in electricity distirbution [BRSH26, BRSH24] . Other application is creating a back up of files on different file servers (obviously there should not be more than one copy of the same file on the same server)[Jan98] . Bin packing problem is NP-hard [GJ79] . FFD is a classical bin packing problem that works as follows: first, the items are ordered by descending size, then in this order it attempts to pack the new item into the first bin, where it fits. In FFD , all the bins are kept open in the order in which they are opened. In their work,[BRSH26] modeled the electricity distribution problem as qBP problem. They applied the generalization of FFD to solve qBP as follows: items are packed using the classical FFD algorithm while satisfying the constraint C1 . The final packing of the input must satisy the constraints C1 and C2 . In their work, they explored the two ways in which an input can be given to the packing algorithms: – In the first way, an input contains q copies of the first item, then q copies of the next item, and so on. – In the second way, an input to the packing algorithm is Dq which is defined asthe q consecutive copies of D where each copy is sorted in non-increasing order. They have argued that in the first way algorithm will generate the packing that contains the numb

FAQs

What is qBP in this paper?

qBP is a bin packing variant where items must be packed into the minimum number of bins subject to capacity limits, with additional constraints: each bin contains at most one copy of each item, and across the packing each item occurs in q different bins.

How is FFDq defined and how does it relate to First Fit Decreasing (FFD)?

FFD first sorts items in non-increasing order and places each item into the first bin where it fits. FFDq generalizes this idea to the qBP setting by analyzing the algorithm on a structured input Dq and a carefully chosen subinstance without losing the intended upper bound for Dq.

What upper bound does the paper prove for special cases?

For certain special cases, the paper shows an approximation bound of the form FFDq(Dq) ≤ (11/9)·OPT(Dq) + (3q), where FFDq is the number of bins produced by the generalized algorithm and OPT(Dq) is the optimal number of bins.

Jul 16, 2026

Upload by Rowan