<p>I am looking for information on a generalization of bin-packing in which each item should appear in exactly <span class="math-container">$k$</span> different bins, for some positive integer <span class="math-container">$k$</span>. The standard bin packing problem corresponds to <span class="math-container">$k=1$</span>. Obviously, the problem is at least as hard as bin packing; I am interested in whether approximation algorithms for bin packing provide good results for <span class="math-container">$k&gt;1$</span>.</p>
<p>At first glance, it seems we could reduce this variant to bin packing by having <span class="math-container">$k$</span> copies of each item (there is a recent algorithm for <a href="https://dl.acm.org/doi/abs/10.1145/3421750" rel="nofollow noreferrer">bin packing with a constant number of item types</a>). However, the problems are different: in my setting, an item cannot appear twice in the same bin.</p>
<p>As an example, suppose the items are x, y, z, all items have size 1, and the bin capacity is 2. With <span class="math-container">$k=1$</span>, we need two bins, e.g. {x,y} and {z}. With <span class="math-container">$k=2$</span>, we need three bins, {x,y} and {y,z} and {z,x}. But if we fill the first two bins with {x,y} and {x,y} then we must use two additional bins {z} and {z}, so we get a sub-optimal solution.</p>
<p>Is anything known about this problem?</p>
<p><sup>Note: the problem is motivated by the practical <a href="https://cstheory.stackexchange.com/questions/49169/the-electricity-packing-problem">electricity packing</a> problem. A solution for the <span class="math-container">$k$</span>-times-bin-packing problem implies a lower bound for the electricity packing problem. Though I am not sure of this lower bound is tight.</sup></p>

CC BY-SA 4.0
2021-10-29T21:19:53.660Z
If $k$ is a fixed constant then the standard aymptotic FPTAS that yields a packing with $(1+\epsilon)OPT + 1$ appears to generalize. Have you tried it?
Chandra Chekuri
CC BY-SA 4.0
2021-10-30T20:51:51.420Z
@ChandraChekuri Do you mean the algorithm by Hoberg and Rothvoss (2017), that finds a packing with OPT+log(OPT) bins?
Erel Segal-Halevi
CC BY-SA 4.0
2021-10-31T03:38:54.793Z
The Asymptotic PTAS is due to de la Vega and Leuker. https://link.springer.com/article/10.1007/BF02579456. Chapter 9 in Vazirani's book on approximation and Chapter 4 in Williamson-Shmoys book cover this material. OPT + log (OPT) is harder result than (1+\eps) OPT + 1.
Chandra Chekuri
<approximation-algorithms><optimization><packing>
Bin packing where each item must occur in $k$ bins
Erel Segal-Halevi
# Bin packing where each item must occur in $k$ bins

(Asked by: username_0 on 2021-10-29)

I am looking for information on a generalization of bin-packing in which each item should appear in exactly $k$ different bins, for some positive integer $k$. The standard bin packing problem corresponds to $k=1$. Obviously, the problem is at least as hard as bin packing; I am interested in whether approximation algorithms for bin packing provide good results for $k>1$.

At first glance, it seems we could reduce this variant to bin packing by having $k$ copies of each item (there is a recent algorithm for [bin packing with a constant number of item types](https://dl.acm.org/doi/abs/10.1145/3421750)). However, the problems are different: in my setting, an item cannot appear twice in the same bin.

As an example, suppose the items are x, y, z, all items have size 1, and the bin capacity is 2. With $k=1$, we need two bins, e.g. {x,y} and {z}. With $k=2$, we need three bins, {x,y} and {y,z} and {z,x}. But if we fill the first two bins with {x,y} and {x,y} then we must use two additional bins {z} and {z}, so we get a sub-optimal solution.

Is anything known about this problem?

Note: the problem is motivated by the practical [electricity packing](https://cstheory.stackexchange.com/questions/49169/the-electricity-packing-problem) problem. A solution for the $k$-times-bin-packing problem implies a lower bound for the electricity packing problem. Though I am not sure of this lower bound is tight.

**Tags:** approximation-algorithms, optimization, packing

> **Comments:**
> **username_1**: If $k$ is a fixed constant then the standard aymptotic FPTAS that yields a packing with $(1+\epsilon)OPT + 1$ appears to generalize. Have you tried it?  
> **username_0**: @ChandraChekuri Do you mean the algorithm by Hoberg and Rothvoss (2017), that finds a packing with OPT+log(OPT) bins?  
> **username_1**: The Asymptotic PTAS is due to de la Vega and Leuker. https://link.springer.com/article/10.1007/BF02579456. Chapter 9 in Vazirani's book on approximation and Chapter 4 in Williamson-Shmoys book cover this material. OPT + log (OPT) is harder result than (1+\eps) OPT + 1.  

---

## 0 answers

