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

Abstract

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, ${\mathrm{TP}}_{\mathcal{A}}$ , that packs each class independently with a BPP algorithm and subsequently merges compatible packing patterns. We prove that the solution returned by ${\mathrm{TP}}_{\mathcal{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 ${\mathrm{TP}}_{\mathcal{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 ${\mathrm{TP}}_{\mathrm{FF}}$ , ${\mathrm{TP}}_{\mathrm{BF}}$ , ${\mathrm{TP}}_{\mathrm{WF}}$ , and their decreasing-order variants all have an absolute worst-case performance ratio exactly 2. If, in addition, is an $\alpha$-approximation algorithm with $\alpha \le 2$, we obtain a finer, component-wise guarantee with factor 2 for the bin-opening cost and factor $\alpha$ for the setup-cost component.