Approxmation Algorithms:

A-18.4 Suppose you work for a major package shipping company, FedUP, as in the pre- vious exercise, but suppose there is a new law that requires every truck to carry no more than M pounds, even if it has room for more boxes. Now the optimiza tion problem is to use the fewest number of trucks possible to carry the n boxes across the country such that each truck is carrying at most M pounds. Describe www.it-ebooks.info Chapter 18. Approximation Algorithms a simple greedy algorithm for assigning boxes to trucks and show that your algo- rithm uses a number of trucks that is within a factor of 2 of the optimal number of trucks. You may assume that no box weighs more than M pounds A-18.4 Suppose you work for a major package shipping company, FedUP, as in the pre- vious exercise, but suppose there is a new law that requires every truck to carry no more than M pounds, even if it has room for more boxes. Now the optimiza tion problem is to use the fewest number of trucks possible to carry the n boxes across the country such that each truck is carrying at most M pounds. Describe www.it-ebooks.info Chapter 18. Approximation Algorithms a simple greedy algorithm for assigning boxes to trucks and show that your algo- rithm uses a number of trucks that is within a factor of 2 of the optimal number of trucks. You may assume that no box weighs more than M pounds