0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$ May 24 at 0:09
  • $\begingroup$ 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). $\endgroup$
    – Rohan Bali
    May 24 at 0:27
  • $\begingroup$ 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? $\endgroup$ May 24 at 1:52
  • $\begingroup$ 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 $\endgroup$
    – Rohan Bali
    May 24 at 14:18
  • 1
    $\begingroup$ 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. epubs.siam.org/doi/10.1137/0217033 $\endgroup$ May 25 at 19:47

0

Your Answer

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