35-1 Bin packing

Suppose that we are given a set of $n$ objects, where the size $s_i$ of the $i$th object satisfies $0 < s_i < 1$. We wish to pack all the objects into the minimum number of unit-size bins. Each bin can hold any subset of the objects whose total size does not exceed $1$.

a. Prove that the problem of determining the minimum number of bins required is $\text{NP-hard}$. ($\textit{Hint:}$ Reduce from the subset-sum problem.)

The first-fit heuristic takes each object in turn and places it into the first bin that can accommodate it. Let $S = \sum_{i = 1}^n s_i$.

b. Argue that the optimal number of bins required is at least $\lceil S \rceil$.

c. Argue that the first-fit heuristic leaves at most one bin less than half full.

d. Prove that the number of bins used by the first-fit heuristic is never more than $\lceil 2S \rceil$.

e. Prove an approximation ratio of $2$ for the first-fit heuristic.

f. Give an efficient implementation of the first-fit heuristic, and analyze its running time.

(Omit!)