Offline green bin packing and its constrained variant

arXiv:2602.16867v1 Announce Type: new
Abstract: In this paper, we study the {em green bin packing} (GBP) problem where $beta ge 0$ and $G in [0, 1]$ are two given values as part of the input. The energy consumed by a bin is $max {0, beta (x-G) }$ where $x$ is the total size of the items packed into the bin. The GBP aims to pack all items into a set of unit-capacity bins so that the number of bins used plus the total energy consumption is minimized. When $beta = 0$ or $G = 1$, GBP is reduced to the classic bin packing (BP) problem. In the {em constrained green bin packing} (CGBP) problem, the objective is to minimize the number of bins used to pack all items while the total energy consumption does not exceed a given upper bound $U$. We present an APTAS and a $frac 32$-approximation algorithm for both GBP and CGBP, where the ratio $frac 32$ matches the lower bound of BP. Keywords: Green bin packing; constrained green bin packing; approximation scheme; offline algorithms