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:
- Worst-Case Analysis of Heuristics for the Bin Packing Problem with General Cost Structures. Here, the cost of a bin is a concave function of the number of items in it, and the goal is to minimize the total cost (rather than the total number of bins).
- Overcommitment in Cloud Services: Bin Packing with Chance Constraints. Here, the load in a bin is a specific submodular function, derived from a setting in which the sizes of items are random.
Are there papers that consider bin-packing with non-additive load functions in a more general way?