Editing Bin packing problem (section)

== Related problems ==
In the bin packing problem, the ''size'' of the bins is fixed and their ''number'' can be enlarged (but should be as small as possible).

In contrast, in the '''[[multiway number partitioning]]''' problem, the ''number'' of bins is fixed and their ''size'' can be enlarged. The objective is to find a partition in which the bin sizes are as nearly equal is possible (in the variant called [[Multiprocessor scheduling|'''multiprocessor scheduling''' problem]] or '''minimum [[makespan]]''' problem, the goal is specifically to minimize the size of the largest bin).

In the '''vector bin packing''' problem, each item is a vector, and the size of each bin is also a vector. Let a bin has size <math>w</math>, and the sum of vectors in the bin be <math>v</math>, then the requirement is that <math>\forall i, v_i \leq w_i</math>.<ref>{{Citation |last=Johnson |first=David S. |title=Vector Bin Packing |date=2016 |encyclopedia=Encyclopedia of Algorithms |pages=2319–2323 |editor-last=Kao |editor-first=Ming-Yang |url=https://link.springer.com/referenceworkentry/10.1007/978-1-4939-2864-4_495 |access-date=2025-05-15 |place=New York, NY |publisher=Springer New York |language=en |doi=10.1007/978-1-4939-2864-4_495 |isbn=978-1-4939-2863-7}}</ref>

In the '''inverse bin packing''' problem,<ref>{{Cite journal|last1=Chung|first1=Yerim|last2=Park|first2=Myoung-Ju|date=2015-01-01|title=Notes on inverse bin-packing problems|url=http://www.sciencedirect.com/science/article/pii/S002001901400180X|journal=Information Processing Letters|language=en|volume=115|issue=1|pages=60–68|doi=10.1016/j.ipl.2014.09.005|issn=0020-0190}}</ref> both the number of bins and their sizes are fixed, but the item sizes can be changed. The objective is to achieve the minimum perturbation to the item size vector so that all the items can be packed into the prescribed number of bins.

In the '''maximum resource bin packing''' problem,<ref name=":02">{{Cite journal|last1=Boyar|first1=Joan|author1-link=Joan Boyar|last2=Epstein|first2=Leah|last3=Favrholdt|first3=Lene M.|last4=Kohrt|first4=Jens S.|last5=Larsen|first5=Kim S.|last6=Pedersen|first6=Morten M.|last7=Wøhlk|first7=Sanne|date=2006-10-11|title=The maximum resource bin packing problem|url=http://www.sciencedirect.com/science/article/pii/S0304397506003483|journal=Theoretical Computer Science|language=en|volume=362|issue=1|pages=127–139|doi=10.1016/j.tcs.2006.06.001|issn=0304-3975}}</ref> the goal is to ''maximize'' the number of bins used, such that, for some ordering of the bins, no item in a later bin fits in an earlier bin. In a dual problem, the number of bins is fixed, and the goal is to minimize the total number or the total size of items placed into the bins, such that no remaining item fits into an unfilled bin.

In the '''[[bin covering problem]]''', the bin size is bounded ''from below'': the goal is to ''maximize'' the number of bins used such that the total size in each bin is at least a given threshold.

In the '''fair indivisible chore allocation''' problem (a variant of '''[[fair item allocation]]'''), the items represent chores, and there are different people each of whom attributes a different difficulty-value to each chore. The goal is to allocate to each person a set of chores with an upper bound on its total difficulty-value (thus, each person corresponds to a bin). Many techniques from bin packing are used in this problem too.<ref>{{cite arXiv|eprint=1907.04505|class=cs.GT|first1=Xin|last1=Huang|first2=Pinyan|last2=Lu|title=An Algorithmic Framework for Approximating Maximin Share Allocation of Chores|date=2020-11-10}}</ref>

In the '''[[guillotine cutting]]''' problem, both the items and the "bins" are two-dimensional rectangles rather than one-dimensional numbers, and the items have to be cut from the bin using end-to-end cuts.

In the '''selfish bin packing''' problem, each item is a player who wants to minimize its cost.<ref>{{Cite journal|last1=Ma|first1=Ruixin|last2=Dósa|first2=György|last3=Han|first3=Xin|last4=Ting|first4=Hing-Fung|last5=Ye|first5=Deshi|last6=Zhang|first6=Yong|date=2013-08-01|title=A note on a selfish bin packing problem|url=https://doi.org/10.1007/s10898-012-9856-9|journal=Journal of Global Optimization|volume=56|issue=4|pages=1457–1462|doi=10.1007/s10898-012-9856-9|issn=0925-5001|s2cid=3082040}}</ref>

There is also a variant of bin packing in which the cost that should be minimized is not the number of bins, but rather a certain [[concave function]] of the number of items in each bin.<ref name="pubsonline.informs.org"/>

Other variants are '''two-dimensional bin packing,'''<ref>Lodi A., Martello S., Monaci, M., Vigo, D. (2010) "Two-Dimensional Bin Packing Problems". In V.Th. Paschos (Ed.), ''Paradigms of Combinatorial Optimization'', Wiley/ISTE, pp.&nbsp;107–129</ref> '''three-dimensional bin packing''',<ref>[https://www.researchgate.net/profile/Leon_Kanavathy/publication/228974015_Optimizing_Three-Dimensional_Bin_Packing_Through_Simulation/links/5890499d92851c9794c62fd0/Optimizing-Three-Dimensional-Bin-Packing-Through-Simulation.pdf Optimizing Three-Dimensional Bin Packing Through Simulation]</ref> '''bin packing with delivery''',<ref>{{cite book |doi=10.1109/BICTA.2010.5645312 |chapter-url=https://www.researchgate.net/publication/221608540 |chapter=Bin Packing/Covering with Delivery, solved with the evolution of algorithms |title=2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA) |date=2010 |last1=Benko |first1=Attila |last2=Dosa |first2=Gyorgy |last3=Tuza |first3=Zsolt |pages=298–302 |isbn=978-1-4244-6437-1 }}</ref>