Question: Suppose you work for a major package shipping company, FedUP, and it is your job to ship a set of n boxes from Rhode Island
Suppose you work for a major package shipping company, FedUP, and it is your job to ship a set of n boxes from Rhode Island to California using a given collection of trucks. You know that these trucks will be weighed at various points along this route and FedUP will have to pay a penalty if any of these trucks are overweight. Thus, you would like to minimize the weight of the most heavily loaded truck. Assuming you know the integer weight of each of the n boxes, describe a simple greedy algorithm for assigning boxes to trucks and show that this algorithm has an approximation ratio of at most 2 for the problem of minimizing the weight of the most heavily loaded truck.
Step by Step Solution
3.33 Rating (159 Votes )
There are 3 Steps involved in it
The greedy algorithm we will use is the next fit algorithm which assigns the next box to the same t... View full answer
Get step-by-step solutions from verified subject matter experts
