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. In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given problem. ... Combinatorics is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. ... In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... Look up Bin in Wiktionary, the free dictionary Bin can refer to: Any container for storing any kind of material or items, usually with a large opening at the top so that contents can easily be removed, often with a lid. ...

There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. They have many applications, such as filling up containers, loading trucks with weight capacity, and creating file backup in removable media.

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). The simpler of these, the First Fit Decreasing strategy, operates by first sorting the items to be inserted in decreasing order by volume, and then inserting each item into the first bin in the list with sufficient remaining space. The sorting step is relatively expensive, but without it we only achieve the looser bound of 17/10 OPT + 2. In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... In computer science, besides the common use as rule of thumb (see heuristic), the term heuristic has two well-defined technical meanings. ...

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 for sufficiently large inputs (this is called an asymptotic polynomial-time approximation scheme). 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. In computer science, approximation algorithms are an approach to attacking NP-hard optimization problems. ... In computer science, a polynomial-time approximation scheme (abbreviated PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). ...

See also

• Partition problem
• Packing problem
• Knapsack problem
• Subset sum problem

The Partition problem is an NP-Complete problem in Computer Science. ... Packing problems are one area where mathematics meets puzzles (recreational mathematics). ... The knapsack problem is a problem in combinatorial optimization. ... The subset sum problem is an important problem in complexity theory and cryptography. ...

References

• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A4.1: SR1, p. 226.

• Vijay V. Vazirani. Approximation Algorithms. Springer. ISBN 3-540-65367-8. p. 74.

• David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SICOMP, Volume 3, Issue 4. 1974.

Michael R. Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NP-completeness. ... David S. Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. ... Vijay Vazirani received his Bachelors degree from MIT in 1979 and his Ph. ...

External links

• PHP Class to pack files without exceeding a given size limit