Bin packing and algorithmic bounds

What you’ll learn

• Apply first-fit, first-fit decreasing and next-fit rules.
• Calculate a lower bound on the number of bins.
• Distinguish a feasible packing from a proven optimum.

Understand the idea

Bin packing places items into equal-capacity bins without exceeding capacity. First fit processes the given item order and places each item in the earliest bin where it fits. Next fit only considers the currently open bin; when an item fails to fit, close that bin and open a new one. These rules can give different results on the same list.

First-fit decreasing begins by sorting the items in descending order, then applies first fit. Keep track of each bin's contents and remaining capacity. A short answer stating only the number of bins hides the algorithm and can miss an infeasible bin.

Dividing total item size by bin capacity and rounding up gives a lower bound. A feasible packing is an upper bound. When the two match, the packing is optimal. When they do not, the algorithm may still be optimal, but the bound alone has not proved it.

Key formulae

$$B\geq\left\lceil\frac{\sum_iw_i}{C}\right\rceil$$

$$\sum_{i\in\text{bin }j}w_i\leq C$$

$$\text{lower bound}\leq B_{\min}\leq\text{number in a feasible packing}$$

Worked example

Use first fit for items (6, 5, 4, 3, 2) in bins of capacity 10. Determine whether the packing is optimal.

1. Place 6 in bin 1 and 5 in bin 2.
2. The item 4 fits in bin 1, making (6, 4). The item 3 then fits in bin 2.
3. The final 2 fits in bin 2, giving (5, 3, 2). Both bins are full.
4. Total size is 20, so the lower bound is $\lceil20/10\rceil=2$. The packing attains it.

Answer: Two bins, (6, 4) and (5, 3, 2); this is optimal.