Editing Bin packing problem (section)

== Non-additive functions ==
There are various ways to extend the bin-packing model to more general cost and load functions:

* Anily, Bramel and Simchi-Levi<ref name="pubsonline.informs.org">{{Cite journal|last1=Anily|first1=Shoshana|last2=Bramel|first2=Julien|last3=Simchi-Levi|first3=David|date=1994-04-01|title=Worst-Case Analysis of Heuristics for the Bin Packing Problem with General Cost Structures|url=https://pubsonline.informs.org/doi/abs/10.1287/opre.42.2.287|journal=Operations Research|volume=42|issue=2|pages=287–298|doi=10.1287/opre.42.2.287|issn=0030-364X}}</ref> study a setting where the cost of a bin is a [[concave function]] of the number of items in the bin. The objective is to minimize the total ''cost'' rather than the number of bins. They show that [[next-fit-increasing bin packing]] attains an absolute worst-case approximation ratio of at most 7/4, and an asymptotic worst-case ratio of 1.691 for any concave and monotone cost function.
* Cohen, Keller, Mirrokni and Zadimoghaddam<ref>{{Cite journal|last1=Cohen|first1=Maxime C.|last2=Keller|first2=Philipp W.|last3=Mirrokni|first3=Vahab|last4=Zadimoghaddam|first4=Morteza|date=2019-07-01|title=Overcommitment in Cloud Services: Bin Packing with Chance Constraints|url=https://pubsonline.informs.org/doi/abs/10.1287/mnsc.2018.3091|journal=Management Science|volume=65|issue=7|pages=3255–3271|doi=10.1287/mnsc.2018.3091|arxiv=1705.09335|s2cid=159270392|issn=0025-1909}}</ref> study a setting where the size of the items is not known in advance, but it is a [[random variable]]. This is particularly common in [[cloud computing]] environments. While there is an upper bound on the amount of resources a certain user needs, most users use much less than the capacity. Therefore, the cloud manager may gain a lot by slight [[Memory overcommitment|overcommitment]]. This induces a variant of bin packing with [[chance constraints]]: the probability that the sum of sizes in each bin is at most ''B'' should be at least ''p'', where ''p'' is a fixed constant (standard bin packing corresponds to ''p''=1). They show that, under mild assumptions, this problem is equivalent to a ''submodular bin packing'' problem, in which the "load" in each bin is not equal to the sum of items, but to a certain [[Submodular set function|submodular function]] of it.