A Tight 2-Approximation Algorithm for the Bin Packing Problem with Setups

We study approximation algorithms for the Bin Packing Problem with Setups (BPPS), a generalization of the classical Bin Packing Problem (BPP) in which items are partitioned into classes and activating a class in a bin consumes a setup weight and incurs a setup cost. We show that direct adaptations of Next Fit (NF), First Fit (FF), Best Fit (BF), and Worst Fit (WF), as well as their decreasing-order variants, have unbounded absolute worst-case performance ratios, even with unit-weight items and zero setup costs. We then introduce a two-phase algorithm, TP_A , that packs each class independently with a BPP algorithm and subsequently merges compatible packing patterns. We prove that the solution returned by TP_A has cost at most twice the optimum under the assumption that produces pairwise merge-maximal solutions, i.e., such that no two packing patterns in the class-wise solution can be feasibly merged. If also runs in polynomial time, this yields a 2-approximation algorithm for the BPPS. The factor is tight: the absolute worst-case performance ratio of TP_A is exactly 2, even when solves every class-wise BPP instance optimally. Since every Any Fit algorithm returns pairwise merge-maximal solutions, it follows that TP_FF , TP_BF , TP_WF , and their decreasing-order variants all have an absolute worst-case performance ratio exactly 2. If, in addition, is an α-approximation algorithm with α≤2, we obtain a finer, component-wise guarantee with factor 2 for the bin-opening cost and factor α for the setup-cost component.