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?

Improve this question
$\endgroup$
2
  • 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
    Dec 29 '21 at 3:04
  • $\begingroup$ @NealYoung yes, it was not a good example. Fixed $\endgroup$
    – Erel Segal-Halevi
    Dec 30 '21 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.