# Approximation Algorithm for Bin packing Variant with Packing Overhead

I recently came up with this bin packing variant and was wondering, if someone has studied it before:

Given: Instance $$I$$ is a set of tuples $$\begin{pmatrix}s_{i} \\ o_{i}\end{pmatrix}$$ with $$s_{i}, o_{i} \leq 1$$ and $$s_{i} \leq o_{i}$$ for all $$i$$. Task: Pack the items in $$I$$ into the least amount of bin with size $$1$$. An item $$i$$ fits into a bin, when the sum of the size of previously packed item leaves enough place for the packing overhead of $$i$$. $$\sum_{j} s_{j} \leq 1-o_{i}$$ Where $$j$$ iterates over all items in the bin. Note that the order in which the items are packed matters: Example: $$i_1 = \begin{pmatrix}0.3 \\ 0.4\end{pmatrix}$$, $$i_2=\begin{pmatrix}0.3 \\ 0.5\end{pmatrix}$$, $$i_3 = \begin{pmatrix}0.1 \\ 0.7\end{pmatrix}$$. When the item are packed in order $$i_1, i_2, i_3$$, then $$i_3$$ will not fit in the first bin, because $$i_1$$ and $$i_2$$ do not leave enough space for the packing overhead of $$i_3$$ ($$s_1 + s_2 > 1 - o_3$$). When $$i_3$$ is packed earlier, than there is enough space for all items in the first bin.

I was not able to find any publications on this or a similar variant. Does anybody know if there is already an approximation algorithm for this kind of problem?

• Obviously you would put the items with smallest difference between size and overhead last (not first). Then for a good solution items with small overhead is valuable so you avoid putting them in the same bin. Interesting problem Commented Nov 29, 2023 at 19:16