You are given a set of n objects, where the size si of the i-th object satisfies 0 < si < 1. Your goal is 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. The first-fit heuristic takes each object in turn and places it into the first bin that can accommodate it, as follows. It maintains an ordered list of bins. Let b denote the number of bins in the list, where b increases over the course of the algorithm, and let < B1, B2, . . . , Bb > be the list of bins. Initially b = 0 and the list is empty. The algorithm takes each object i in turn and places it in the lowest-numbered bin that can still accommodate it. If no bin can accommodate object i, then b is incremented and a new bin Bb is opened, containing object i. Let S = Pn i=1 si .
1. Argue that the optimal number of bins required is at least dSe.
2. Argue that the first-fit heuristic leaves at most one bin at most half full.
3. Prove that the number of bins used by the first-fit heuristic never exceeds d2Se.
4. Prove an approximation ratio of 2 for the first-fit heuristic.