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?

  • $\begingroup$ 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 $\endgroup$
    – gnasher729
    Commented Nov 29, 2023 at 19:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.