Editing Bin packing problem (section)

== Hardness of bin packing ==
The bin packing problem is [[Strong NP-completeness|strongly NP-complete]]. This can be proven by reducing the strongly NP-complete [[3-partition problem]] to bin packing.<ref name="GareyJohnson2" />

Furthermore, there can be no [[approximation algorithm]] with absolute approximation ratio smaller than <math>\tfrac 3 2</math> unless <math>\mathsf{P} = \mathsf{NP}</math>. This can be proven by a reduction from the [[partition problem]]:<ref>{{cite book|last1=Vazirani|first1=Vijay V.|title=Approximation Algorithms|date=14 March 2013|publisher=Springer Berlin Heidelberg|isbn=978-3662045657|pages=74}}</ref> given an instance of Partition where the sum of all input numbers is <math>2T</math>,  construct an instance of bin-packing in which the bin size is {{mvar|T}}. If there exists an equal partition of the inputs, then the optimal packing needs 2 bins; therefore, every algorithm with an approximation ratio smaller than {{sfrac|3|2}} must return less than 3 bins, which must be 2 bins. In contrast, if there is no equal partition of the inputs, then the optimal packing needs at least 3 bins.

On the other hand, bin packing is solvable in [[pseudo-polynomial time]] for any fixed number of bins {{mvar|K}}, and solvable in polynomial time for any fixed bin capacity {{mvar|B}}.<ref name="GareyJohnson2" />