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.
