Consider the Bin-Packing Problem with items of size wi , i 

1, 2, . . . , n, such that 0 < wi ≤ 1. The objective is find the minimum number of unit size bins b

∗ needed to pack all the items without violating the capacity constraint.

(a) Show that

n i1 wi is a lower bound on b

∗.

(b) Define a locally optimal solution to be one where no two bins can be feasibly combined into one. Showthat any locally optimal solution uses no more than twice the minimum number of bins, that is, no more than 2b

∗ bins.

(c) The Next-Fit Heuristic is the following. Start by packing the first item in bin 1. Then, each subsequent item is packed in the last opened bin if possible,

or else a new bin is opened and it is placed there. Show that the Next-Fit Heuristic produces a solution with at most 2b ∗ bins.