Most of the research on bin-packing algorithms starts in the 1970s and the 1980s, in the USA. One of the noted researchers, Ron Graham, is also a talented juggler and former circus performer.

The problem of getting the *best* bin-packing is one of the “NP-complete” category of “intractable” problems.

(1) There is no known exact algorithm for these problems which doesn’t become unworkable (require hundreds of years or a computer bigger than the Earth, etc.) for large numbers of items.

(2) There is, however, a workable algorithm to *check a proposed solution*.

(3) No-one knows whether a workable exact algorithm can be devised to *find* a solution, rather than check one; but *if* if a workable exact algorithm can be devised for one of these “NP-complete” problems, then (it has been proven) a workable exact algorithm can be devised for all the other “NP-complete” problems too.

Most mathematicians think that no workable exact algorithm can be found for the “NP-complete” problems, but no-one has proved it yet. (This is called the “P-vs-NP problem”).

Quite a few common problems are also “intractable”, for example the problem of how to design a timetable for a school which avoids clashes and fits the maximum number of student preferences. All known algorithms for bin-packing are approximations which may tell us to use more bins than are necessary. Likewise, all known algorithms for timetabling are only approximations.

**First fit:** time of the order of N log N for N items

May give up to 2 times the optimal number of bins

**First fit decreasing:** workable only if we can survey all the items before packing (rather than having to pack them as they arrive)

Time of the order of N log N for sorting, plus another N log N for fitting

Uses at most (4M + 1)/3 bins if the optimal is M

**Full-bin:** also workable only if we can survey all the items before packing (rather than having to pack them as they arrive)

Calculation time of the order of 2^{N} (which means over a hundred years on a modern computer for a problem with just 60 items…)

Does not necessarily give a good solution. Suppose the bins have size 12, and we have items of size 4, 7, 4, 7, 4, 7. The full-bin packing algorithm will tell us to take four bins – 4+4+4, 7, 7, and 7 – though First Fit would give us three bins, 4+7, 4+7, 4+7. (And in real life, of course, there will often be *no* combination of items that fills a bin *exactly*. I don’t know where the Edexcel book got “Full-bin” from. Not real life).

Contrary to what your textbook says, an algorithm for the best bin-packing is possible. Just try out every single combination of items and bins, and eventually you will find the best one. The problem is that for even quite small numbers of items, this try-out-every-possibility algorithm involves too much calculation to be workable even with the fastest computer.

There are also many problems which are *not computable*, that is, we can *prove* that *no* algorithm exists to solve them, not even an unworkably long one. For example, this problem: find an algorithm to check equations of the type xy^{2}-2x^{2}+3=0 (polynomials in x and y with whole-number coefficients), and decide whether they have a whole-number solution. (For example, x^{2}+y^{2}=25 does, but x^{2}+y^{2}=24 doesn’t).

http://www.ams.org/samplings/feature-column/fcarc-bins1

https://www.cs.ucsb.edu/~suri/cs130b/BinPacking.txt

*Ron Graham*