You are consulting for a trucking company that does a large amount of business s

Question

You are consulting for a trucking company that does a large amount of business shipping packages between New York and Boston. The volume is high enough that they have to send a number of trucks each day between the two locations. Trucks have a xed limit W on the maximum amount of weight they are allowed to carry. Boxes arrive at the New York station one by one, and each package i has weight wi. The trucking station is quite small, so at most one truck can be at the station at any time. Company policy requires that boxes are shipped in the order they arrive; otherwise, a customer might get upset upon seeing a box that arrived after his make it to Boston faster. At the moment, the company is using a simple greedy algorithm for packing: they pack boxes in the order they arrive, and whenever the next box does not fit, they send the truck on its way. They wonder if they might be using too many trucks, and they want your opinion on whether the situation can be improved. Here is how they are thinking. Maybe one could decrease the number of truck needed by sometimes sending o a truck that was less than full, and in this way allow the next few trucks to be better packed. Prove that, for a given set of boxes with speci ed weights, the greedy algorithm currently in use actually minimizes the number of trucks that are needed. Your proof should follow the type of analysis we used for the Interval Scheduling Problem: it should establish the optimality of this greedy packing algorithm by identifying a measure under which it "stays ahead" of all other solutions.
Also analyze the computing complexity of the greedy algorithm that you have proposed

Explanation / Answer

Consider the solution given by the greedy algorithm as a sequence of packages, here represented by indexes: 1, 2, 3, ... n. Each package i has a weight, w_i, and an assigned truck t_i. { t_i } is a non-decreasing sequence (as the k'th truck is sent out before anything is placed on the k+1'th truck). If t_n = m, that means our solution takes m trucks to send out the n packages.

If the greedy solution is non-optimal, then there exists another solution { t'_i }, with the same constraints, s.t. t'_n = m' < t_n = m.

Consider the optimal solution that matches the greedy solution as long as possible, so or all i < k, t_i = t'_i, and t_k != t'_k.
t_k != t'_k => Either

1) t_k = 1 + t'_k
     i.e. the greedy solution switched trucks before the optimal solution.

     But the greedy solution only switches trucks when the current truck is full. Since t_i = t'_i i < k, the contents of the current truck after adding the k - 1'th package are identical for the greedy and the optimal solutions.
     So, if the greedy solution switched trucks, that means that the truck couldn't fit the k'th package, so the optimal solution must switch trucks as well.

     So this situation cannot arise.

   2) t'_k = 1 + t_k
      i.e. the optimal solution switches trucks before the greedy solution.

      Construct the sequence { t"_i } s.t.
        t"_i = t_i, i <= k
        t"_k = t'_i, i > k

This is the same as the optimal solution, except package k has been moved from truck t'_k to truck (t'_k - 1). Truck t'_k cannot be overpacked, since it has one less packages than it did in the optimal solution, and truck (t'_k - 1) cannot be overpacked, since it has no more packages than it did in the greedy solution.

So { t"_i } must be a valid solution. If k = n, then we may have decreased the number of trucks required, which is a contradiction of the optimality of { t'_i }. Otherwise, we did not increase the number of trucks, so we created an optimal solution that matches { t_i } longer than { t'_i } does, which is a contradiction of the definition of { t'_i }.

    So the greedy solution must be optimal.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.