CS105 W11: Homework 08

1. KT 11.1. For part (a) explain how to get examples that are arbitrarily close to 2 times optimal.
2. KT 11.4. Give an example that achieves a factor of b times optimal.
3. KT 11.5
4. KT 11.8
5. KT 11.10
6. KT 11.11
7. KT 12.2

1. Do problem 1 with the following modification to the algorithm: All of the trucks are lined up at the loading dock, and you put the next item into the first truck into which it will fit. All of the trucks leave at the end. For part (a) give an example that is 5/3 times optimal. For lots more extra credit give an example that is 17/10 times optimal.