Bin packing problem
|
|
In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used.
There are a lot of variations of this problem (2D packing, linear packing, packing by weight, packing by cost, etc...) most of them with many applications, such as filling up containers, loading trucks with weight capacity, creating file backup in removable media, etc...
Since it is NP-hard, the most efficient known algorithms use heuristics to accomplish very good results in most cases, which may not be the optimal solution. The Best Fit Decreasing and First Fit Decreasing strategies use no more than 11/9 OPT + 4 bins (where OPT is the number of bins given by the optimal solution). Although these simple strategies are often good enough, efficient approximation algorithms have been demonstrated that can solve the bin packing problem within any fixed percentage of the optimal solution. This is an advantage the problem has over many other common NP-hard problems, some of which cannot be approximated within any constant factor at all.