Bin packing: four greedy rules, one hard problem

How to read this

Columns are bins of capacity 1 (the dashed line at the top). Items stack from the bottom; the number on a block is its size. The strip above shows the items in the order the rule processes them.

The four rules. Next Fit keeps only the newest bin open. First Fit scans bins left to right and uses the first with room. First-Fit Decreasing sorts the items largest first, then runs First Fit. Best Fit picks the bin that would be left fullest (least room to spare).

Lower bound. Every bin holds at most 1, so any packing needs at least ⌈Σ sizes⌉ bins. bins / ⌈Σ⌉ therefore overestimates the true accuracy ratio. For small inputs (n ≤ 14) the table also finds the true optimum by exhaustive backtracking, so you see the exact ratio bins / OPT.

Known guarantees (Levitin §12.3 and exercises): FF uses at most about 1.7·OPT bins, FFD at most about (11/9)·OPT + a small constant (a simpler, easier-to-prove bound is 1.5), and NF at most 2·OPT. On random inputs all of them do much better.

Try this

1. Classic example 0.4, 0.2, 0.6, 0.7. Predict FF's result: 0.4 and 0.2 share bin 1, 0.6 no longer fits there, 0.7 fits nowhere, so 3 bins. FFD sorts first (0.7, 0.6, 0.4, 0.2) and needs only 2 = ⌈1.9⌉, which is optimal.
2. Next Fit trap (0.5, 0.1, 0.5, 0.1, …): NF opens a new bin for almost every 0.5 while FF tucks every 0.1 into an earlier bin. Count the bins for each.
3. First Fit's bad family: six items each of 0.15, 0.34 and 0.51. The optimum packs one of each per bin (6 bins, all exactly full), but FF in this order uses 10: ratio 5/3. Does FFD fix it?
4. Random experiment with n = 30 and uniform sizes: the average bins / ⌈Σ⌉ for FFD is typically only a few percent above 1. Switch the distribution to “small”: which rule suffers most?
5. With Predict mode on, guess the bin for each item under Best Fit, then rerun under First Fit. When do they disagree?