Editing Bin packing problem (section)

=== Computational complexity ===
Mandal, Chakrabary and Ghose<ref name=":03" /> proved that BP-SPF is [[NP-hardness|NP-hard]].

Menakerman and Rom<ref>Nir Menakerman and Raphael Rom "Bin Packing with Item Fragmentation". Algorithms and Data Structures, 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001, Proceedings.</ref> showed that BP-SIF and BP-SPF are both [[strongly NP-hard]]. Despite the hardness, they present several algorithms and investigate their performance. Their algorithms use classic algorithms for bin-packing, like [[Next-fit bin packing|next-fit]] and [[First-fit-decreasing bin packing|first-fit decreasing]], as a basis for their algorithms.

Bertazzi, Golden and Wang<ref>{{Cite journal |last1=Bertazzi |first1=Luca |last2=Golden |first2=Bruce |last3=Wang |first3=Xingyin |date=2019-05-31 |title=The Bin Packing Problem with Item Fragmentation:A worst-case analysis |journal=Discrete Applied Mathematics |series=GO X Meeting, Rigi Kaltbad (CH), July 10--14, 2016 |language=en |volume=261 |pages=63–77 |doi=10.1016/j.dam.2018.08.023 |issn=0166-218X |s2cid=125361557|doi-access=free }}</ref> introduced a variant of BP-SIF with <math>1-x</math> split rule: an item is allowed to be split in only one way according to its size. It is useful for the [[vehicle routing problem]] for example. In their paper, they provide the worst-case performance bound of the variant.

Shachnai, Tamir and Yehezkeli<ref>{{Cite book |last1=Shachnai |first1=Hadas |last2=Tamir |first2=Tami |last3=Yehezkely |first3=Omer |title=Approximation and Online Algorithms |chapter=Approximation Schemes for Packing with Item Fragmentation |date=2006 |editor-last=Erlebach |editor-first=Thomas |editor2-last=Persinao |editor2-first=Giuseppe |chapter-url=https://link.springer.com/chapter/10.1007/11671411_26 |series=Lecture Notes in Computer Science |language=en |location=Berlin, Heidelberg |publisher=Springer |volume=3879 |pages=334–347 |doi=10.1007/11671411_26 |isbn=978-3-540-32208-5}}</ref> developed approximation schemes for BP-SIF and BP-SPF; a dual [[Polynomial-time approximation scheme|PTAS]] (a PTAS for the dual version of the problem), an asymptotic PTAS called APTAS, and a dual asymptotic [[FPTAS]] called AFPTAS for both versions.

Ekici<ref>{{Cite journal |last=Ekici |first=Ali |date=2021-02-01 |title=Bin Packing Problem with Conflicts and Item Fragmentation |url=https://www.sciencedirect.com/science/article/pii/S0305054820302306 |journal=Computers & Operations Research |language=en |volume=126 |pages=105113 |doi=10.1016/j.cor.2020.105113 |issn=0305-0548 |s2cid=225002556}}</ref> introduced a variant of BP-SPF in which some items are in conflict, and it is forbidden to pack fragments of conflicted items into the same bin. They proved that this variant, too, is NP-hard.

Cassazza and Ceselli<ref>{{Cite journal |last1=Casazza |first1=Marco |last2=Ceselli |first2=Alberto |date=2014-06-01 |title=Mathematical programming algorithms for bin packing problems with item fragmentation |url=https://www.sciencedirect.com/science/article/pii/S0305054813003596 |journal=Computers & Operations Research |language=en |volume=46 |pages=1–11 |doi=10.1016/j.cor.2013.12.008 |issn=0305-0548}}</ref> introduced a variant with no cost and no overhead, and the number of bins is fixed. However, the number of fragmentations should be minimized. They present mathematical programming algorithms for both exact and approximate solutions.