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?

• 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? Commented Dec 29, 2021 at 3:04
• @NealYoung yes, it was not a good example. Fixed Commented Dec 30, 2021 at 12:36
• 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. Commented Oct 1, 2022 at 16:58