Bin packing

Suppose that we are given a set of n objects, where the size si of the ith object satisfies 0 < si <

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 NPhard.

(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

b. Argue that the optimal number of bins required is at least [S].

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 [2S].

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.