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.
• 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? Dec 29, 2021 at 3:04