The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, splitting a network prefix into multiple subnets,[5] and technology mapping in FPGA semiconductor chip design.
Despite its worst-case hardness, optimal solutions to very large instances of the problem can be produced with sophisticated algorithms.
It requires Θ(n log n) time, where n is the number of items to be packed.
It is known, however, that there always exists at least one ordering of items that allows first-fit to produce an optimal solution.
Specifically, a set of items could occupy less space when packed together than the sum of their individual sizes.
This variant is known as VM packing[7] since when virtual machines (VMs) are packed in a server, their total memory requirement could decrease due to pages shared by the VMs that need only be stored once.
If items can share space in arbitrary ways, the bin packing problem is hard to even approximate.
In Computers and Intractability[8]: 226 Garey and Johnson list the bin packing problem under the reference [SR1].
This can be proven by reducing the strongly NP-complete 3-partition problem to bin packing.
In contrast, if there is no equal partition of the inputs, then the optimal packing needs at least 3 bins.
A diverse set of offline and online heuristics for bin-packing have been studied by David S. Johnson on his Ph.D.
These heuristics usually keep several classes of open bins, devoted to items of different size ranges (see the linked pages for more information): Yao[15] proved in 1980 that there can be no online algorithm with an asymptotic competitive ratio smaller than
Johnson[11] proved that any AnyFit scheme A that runs on a list ordered by descending size has an asymptotic approximation ratio of
.Some methods in this family are (see the linked pages for more information): Fernandez de la Vega and Lueker[29] presented a PTAS for bin packing.
This yields an instance with a small number of different sizes, which can be solved exactly using the configuration linear program.
[30] The Karmarkar-Karp bin packing algorithm finds a solution with size at most
A faster alternative is the Bin Completion algorithm proposed by Korf in 2002[35] and later improved.
A special case of bin packing is when there is a small number d of different item sizes.
This case is also called high-multiplicity bin packing, and It admits more efficient algorithms than the general problem.
Bin-packing with fragmentation or fragmentable object bin-packing is a variant of the bin packing problem in which it is allowed to break items into parts and put each part separately on a different bin.
Breaking items into parts may allow for improving the overall performance, for example, minimizing the number of total bin.
Menakerman and Rom[39] showed that BP-SIF and BP-SPF are both strongly NP-hard.
Cassazza and Ceselli[43] introduced a variant with no cost and no overhead, and the number of bins is fixed.
They present mathematical programming algorithms for both exact and approximate solutions.
The problem of fractional knapsack with penalties was introduced by Malaguti, Monaci, Paronuzzi and Pferschy.
[44] They developed an FPTAS and a dynamic program for the problem, and they showed an extensive computational study comparing the performance of their models.
An important special case of bin packing is that the item sizes form a divisible sequence (also called factored).
If the item sizes are divisible, then some of the heuristic algorithms for bin packing find an optimal solution.
The objective is to find a partition in which the bin sizes are as nearly equal is possible (in the variant called multiprocessor scheduling problem or minimum makespan problem, the goal is specifically to minimize the size of the largest bin).
In the selfish bin packing problem, each item is a player who wants to minimize its cost.