Suppose you work for a major package shipping company FedUP

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.

Solution

Consider instance p=2 and weight W = {1,2,1,2}. Now greedy algorithm will load 1 into 1st truck and then if we add second weight to 1st truck, it will become heavy.So we will load this second weight to 2nd truck. Then assume 2nd truck is full so 2nd truck will start transporting. So this process continues for remaining trucks. here optimal number of trucks are three.

So for p>4 the set of weights are as follows W = {1,K,1,K ... 1,K} and for k>1. we required p/2 trucks to fill weights k and [p/2K] trucksf for denomination weight 1.

So equation will be p/2 + {p/2k} <= p/2k + 1 <= 3p/4 + 1 <= p trucks.