2
$\begingroup$

I am looking for information on the bin packing problem, where the load of each bin is not the sum of items in the bin, but some other monotone set function. For example, suppose each item $i$ has size $s_i\geq 1$, and the load of each set $X$ of items equals $\sum_{i\in X} s_i + \sqrt{|X|}$. We are allowed to put, in each bin, a subset of items for which the total load is at most the bin capacity. The objective is to minimize the number of bins.

There are many possible load functions. I am particularly interested in submodular or supermodular set functions, and in fast heuristics that guarantee a constant-factor approximation to the optimal number of bins. So far, I found only two related papers:

Are there papers that consider bin-packing with non-additive load functions in a more general way?

$\endgroup$
3
  • 1
    $\begingroup$ In your example isn't it just that $\sum_{i\in X} s_i - |X|$ equals $\sum_{i\in X} (s_i-1)$, so that your example is equivalent to standard bin packing with sizes $s'_i = s_i - 1$? Or am I missing something? $\endgroup$
    – Neal Young
    Commented Dec 29, 2021 at 3:04
  • $\begingroup$ @NealYoung yes, it was not a good example. Fixed $\endgroup$ Commented Dec 30, 2021 at 12:36
  • 1
    $\begingroup$ If you consider submodular or supermodular functions it is easy to find problems where packing one bin effectively is very hard. It then makes the overall bin packing problem hard (provably in some cases) and likely to be hard (but may require technical work) in other cases. For instance if you take a graph $G=(V,E)$ and consider the supermodular function $f(S) = |E(S)|$ then packing into $m$ bins of capacity $0$ is same as coloring $G$ with $m$ colors. Relaxations of coloring are also hard etc. $\endgroup$ Commented Oct 1, 2022 at 16:58

1 Answer 1

1
$\begingroup$

In addition to the papers you cited, there are two others I'm aware of:

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.