<p>I have a decision problem that I cannot seem to map to a standard studied problem, although it seems similar to a few. I am wondering if anyone has come across this problem before, or if someone can identify a standard name for this problem?</p>
<p>The decision problem is to check if a set of items (given size) can be assigned to a set of bins with each bin shrinking the size of the item by a scalar number, such that each bin contains at-least some scaled total size.</p>
<p><strong>Formalizing</strong> <br/></p>
<p>Assume we have n items in a list. Each of these has a positive size.</p>
<p>List of items <span class="math-container">$L = (a_i, a_2 ,... , a_n)$</span> <br />
Size of an items <span class="math-container">$a_i$</span> is given by <span class="math-container">$s(a_i) ∈ ℝ⁺, i ∈ [1, n]$</span></p>
<p>We have have m bins, each we wish to fill so that it contains a total size of C or more.</p>
<p>Furthermore, each bin has a size compressor associated with it. The size compressor scales down the size of any item in that bin.</p>
<p>Size compressor <span class="math-container">$W_i ∈ (0, 1], i ∈ [1, m]$</span></p>
<p>Hence if some set of items <span class="math-container">$S_i \subseteq L $</span> are assigned to bin i, the total size of items in the bin can be given as</p>
<p><span class="math-container">$$W_i * \sum_{a∈S_i} s(a)$$</span>.</p>
<p>The decision problem then is, can these n items be assigned to these m bins such that the total size of items in each bin is greater than C?</p>
<p><strong>Similar Problems</strong> <br/></p>
<p>It seems to me that this problem is similar to a few standard problems, but I can't seem to map it exactly to a problem I know. Most problems this seems to be similar to are NP Hard, so I think my problem is also NP Hard. I am thus hoping to map it to a known and studied problem so I can leverage a known approximate algorithms.</p>
<p>If <span class="math-container">$W_i$</span> = 1, i.e. no size compression, the problem could be constructed as a <em>standard bin covering problem</em>. The solution to this standard problem gives us the maximum number of bins that could be filled under this constraint, and comparing it to m would give us a solution to the decision problem. I tried looking for bin covering problems with variable bin sizes, to accommodate <span class="math-container">$W_i ∈ (0, 1]$</span>, but this search came up empty.</p>
<p>Similarly, with the same assumption of <span class="math-container">$W_i$</span> = 1, one could construct this as a <em>multiway number partitioning problem</em>. Here, we would get the minimum total size that could be assigned to a bin under roughly equal size assignment, and compare it to C to give us a solution to our decision problem. I tried looking for multiway number partitioning problem with unequal partition sizes, to accommodate <span class="math-container">$W_i ∈ (0, 1]$</span>, but this search came up empty.</p>
<p>Finally, it could be constructed as <em>max-min fair item allocation problem</em>. Here each bin assigns a subjective &quot;value&quot; (for us weight) to each item, and the goal is to maximize the minimum value each bin is allocated. While we can map our problem to this one, I feel like our problem should be somewhat easier to solve since the weight assigned to any bin is not arbitrary but some fixed scalar multiple of an inherent value. Here again, I couldn't find similar works.</p>
<p>We can try solving this problem using 0-1 integer linear programming, but I don't know if it is easy to show that the solutions we get are provably approximate.</p>

CC BY-SA 4.0
2023-05-24T00:09:19.190Z
What is the context in which this problem arose? Feels like a homework problem since it is quite easy to prove it is NP-Complete with $W_i = 1$ for all $i$ and $m=2$.
Chandra Chekuri
CC BY-SA 4.0
2023-05-24T00:27:28.307Z
Thanks for your reply. Unfortunately, it is not a home work problem. It arose in the context of a quantum networking research where a single source is trying to assign resources to pairs of nodes in an undirected weighted graph. Resources can only be assigned in blocks. Each pair needs C resources after loss. Yes, I agree that that with Wi = 1 the problem reduces to a known one (I make mention of this in the original post near where i talk about  reduction to the bin covering problem).
Rohan Bali
CC BY-SA 4.0
2023-05-24T01:52:03.967Z
I am confused. If all $W_i$ are $1$ then the problem is at least as hard as bin covering. By scaling this also shows that for any fixed $\alpha$ where $W_i = \alpha$ for all $i$ the problem is hard. I am not sure what you are asking for. Are the $W_i$ some fixed constants that are not part of the input?
Chandra Chekuri
CC BY-SA 4.0
2023-05-24T14:18:11.360Z
Yes, that is correct, $W_i$'s are fixed values I don't have control over. Ultimately, I am trying to find efficient approximate algorithms to solve this problem. E.g. I have 6 items with sizes [1, 3, 5,10, 3, 8] and four bins with $W_i$’s [0.5, 0.9, 0.2, 0.4]. I want to fill each bin so it is filled to at least a scaled size of 5 each. I am looking for an efficient approximate algorithm that could answer this question
Rohan Bali
CC BY-SA 4.0
2023-05-25T19:47:12.713Z
Since the problem is NP-hard even for $m=2$ and $W_i=1$ for all $i$ you need to relax the constraint. If you want to ensure that each bin is filled to at least $(1-\epsilon)C$ then it may be possible to do it for any fixed $\epsilon > 0$ in polynomial time. The related problem here is to schedule jobs to minimize makespan when processors have different speeds. https://epubs.siam.org/doi/10.1137/0217033
Chandra Chekuri
<approximation-algorithms><partition-problem><packing><subset-sum><covering-problems>
Bin Covering problem with variable bin sizes
Rohan Bali
# Bin Covering problem with variable bin sizes

(Asked by: username_0 on 2023-05-23)

I have a decision problem that I cannot seem to map to a standard studied problem, although it seems similar to a few. I am wondering if anyone has come across this problem before, or if someone can identify a standard name for this problem?

The decision problem is to check if a set of items (given size) can be assigned to a set of bins with each bin shrinking the size of the item by a scalar number, such that each bin contains at-least some scaled total size.

**Formalizing**

Assume we have n items in a list. Each of these has a positive size.

List of items $L = (a\_i, a\_2 ,... , a\_n)$   
Size of an items $a\_i$ is given by $s(a\_i) ∈ ℝ⁺, i ∈ [1, n]$

We have have m bins, each we wish to fill so that it contains a total size of C or more.

Furthermore, each bin has a size compressor associated with it. The size compressor scales down the size of any item in that bin.

Size compressor $W\_i ∈ (0, 1], i ∈ [1, m]$

Hence if some set of items $S\_i \subseteq L $ are assigned to bin i, the total size of items in the bin can be given as

$$W\_i \* \sum\_{a∈S\_i} s(a)$$.

The decision problem then is, can these n items be assigned to these m bins such that the total size of items in each bin is greater than C?

**Similar Problems**

It seems to me that this problem is similar to a few standard problems, but I can't seem to map it exactly to a problem I know. Most problems this seems to be similar to are NP Hard, so I think my problem is also NP Hard. I am thus hoping to map it to a known and studied problem so I can leverage a known approximate algorithms.

If $W\_i$ = 1, i.e. no size compression, the problem could be constructed as a *standard bin covering problem*. The solution to this standard problem gives us the maximum number of bins that could be filled under this constraint, and comparing it to m would give us a solution to the decision problem. I tried looking for bin covering problems with variable bin sizes, to accommodate $W\_i ∈ (0, 1]$, but this search came up empty.

Similarly, with the same assumption of $W\_i$ = 1, one could construct this as a *multiway number partitioning problem*. Here, we would get the minimum total size that could be assigned to a bin under roughly equal size assignment, and compare it to C to give us a solution to our decision problem. I tried looking for multiway number partitioning problem with unequal partition sizes, to accommodate $W\_i ∈ (0, 1]$, but this search came up empty.

Finally, it could be constructed as *max-min fair item allocation problem*. Here each bin assigns a subjective "value" (for us weight) to each item, and the goal is to maximize the minimum value each bin is allocated. While we can map our problem to this one, I feel like our problem should be somewhat easier to solve since the weight assigned to any bin is not arbitrary but some fixed scalar multiple of an inherent value. Here again, I couldn't find similar works.

We can try solving this problem using 0-1 integer linear programming, but I don't know if it is easy to show that the solutions we get are provably approximate.

**Tags:** approximation-algorithms, partition-problem, packing, subset-sum, covering-problems
> **Comments:**
> **username_1**: What is the context in which this problem arose? Feels like a homework problem since it is quite easy to prove it is NP-Complete with $W_i = 1$ for all $i$ and $m=2$.  
> **username_0**: Thanks for your reply. Unfortunately, it is not a home work problem. It arose in the context of a quantum networking research where a single source is trying to assign resources to pairs of nodes in an undirected weighted graph. Resources can only be assigned in blocks. Each pair needs C resources after loss. Yes, I agree that that with Wi = 1 the problem reduces to a known one (I make mention of this in the original post near where i talk about  reduction to the bin covering problem).  
> **username_1**: I am confused. If all $W_i$ are $1$ then the problem is at least as hard as bin covering. By scaling this also shows that for any fixed $\alpha$ where $W_i = \alpha$ for all $i$ the problem is hard. I am not sure what you are asking for. Are the $W_i$ some fixed constants that are not part of the input?  
> **username_0**: Yes, that is correct, $W_i$'s are fixed values I don't have control over. Ultimately, I am trying to find efficient approximate algorithms to solve this problem. E.g. I have 6 items with sizes [1, 3, 5,10, 3, 8] and four bins with $W_i$’s [0.5, 0.9, 0.2, 0.4]. I want to fill each bin so it is filled to at least a scaled size of 5 each. I am looking for an efficient approximate algorithm that could answer this question  
> **username_1**: Since the problem is NP-hard even for $m=2$ and $W_i=1$ for all $i$ you need to relax the constraint. If you want to ensure that each bin is filled to at least $(1-\epsilon)C$ then it may be possible to do it for any fixed $\epsilon > 0$ in polynomial time. The related problem here is to schedule jobs to minimize makespan when processors have different speeds. https://epubs.siam.org/doi/10.1137/0217033  

---

## 0 answers

