<p>In addition to the papers you cited, there are two others I'm aware of:</p>
<ul>
<li><a href="http://math.haifa.ac.il/lea/GCBP.pdf" rel="nofollow noreferrer">Bin packing with general cost structures</a></li>
<li><a href="https://onlinelibrary.wiley.com/doi/10.1002/nav.20142" rel="nofollow noreferrer">Bin packing problem with concave costs of bin utilization</a></li>
</ul>

CC BY-SA 4.0
2022-09-27T19:33:00.887Z
2022-09-27T19:33:00.887Z
Gal Kaminka
<p>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 <span class="math-container">$i$</span> has size <span class="math-container">$s_i\geq 1$</span>, and the load of each set <span class="math-container">$X$</span> of items equals <span class="math-container">$\sum_{i\in X} s_i + \sqrt{|X|}$</span>.
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.</p>
<p>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:</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Bin_packing_problem#cite_note-39" rel="nofollow noreferrer">Worst-Case Analysis of Heuristics for the Bin Packing Problem with General Cost Structures</a>. 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).</li>
<li><a href="https://pubsonline.informs.org/doi/abs/10.1287/mnsc.2018.3091" rel="nofollow noreferrer">Overcommitment in Cloud Services: Bin Packing with Chance Constraints</a>. Here, the load in a bin is a specific submodular function, derived from a setting in which the sizes of items are random.</li>
</ul>
<p>Are there papers that consider bin-packing with non-additive load functions in a more general way?</p>

CC BY-SA 4.0
2021-12-29T03:04:41.587Z
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?
Neal Young
CC BY-SA 4.0
2021-12-30T12:36:22.353Z
@NealYoung yes, it was not a good example. Fixed
Erel Segal-Halevi
CC BY-SA 4.0
2022-10-01T16:58:43.907Z
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.
Chandra Chekuri
<reference-request><co.combinatorics>
Bin packing with non-additive load functions
Erel Segal-Halevi
# Bin packing with non-additive load functions

(Asked by: username_0 on 2021-12-28)

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](https://en.wikipedia.org/wiki/Bin_packing_problem#cite_note-39). 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](https://pubsonline.informs.org/doi/abs/10.1287/mnsc.2018.3091). 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?

**Tags:** reference-request, co.combinatorics
> **Comments:**
> **username_1**: 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?  
> **username_0**: @NealYoung yes, it was not a good example. Fixed  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2022-09-27. Score: 1

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

* [Bin packing with general cost structures](http://math.haifa.ac.il/lea/GCBP.pdf)
* [Bin packing problem with concave costs of bin utilization](https://onlinelibrary.wiley.com/doi/10.1002/nav.20142)


---

