BIN PACKING

First Fit Decreasing vs First Fit — comparing heuristics

20
100
2x
Bin Packing is NP-hard: given items of various sizes, pack them into the fewest bins of fixed capacity. The First Fit Decreasing (FFD) heuristic sorts items from largest to smallest, then places each in the first bin with room — it uses at most (11/9)OPT + 6/9 bins (tight bound). First Fit without sorting can use up to 1.7·OPT bins. The gap between best heuristic and true optimum is actively studied. Bin packing appears in cloud resource allocation, file backup across DVDs, and compiler register assignment.