Consider the following problem. Suppose that we have n truckloads of goods l 1,…
ID: 2247330 • Letter: C
Question
Consider the following problem. Suppose that we have n truckloads of goods l1,……ln that need to be transported to various destinations. We also have n truck/drivers, t1,…tn that each charge a (potentially different) fee to haul a particular truckload. Moreover, each truck can only carry one load and we wish to transport all loads. Let c(I,j) be the cost of transporting load I using truck j.
1) Prove or disprove: the above problem is NP-complete. If you prove, provide a reduction from any NP-complete problem. If you disprove, provide a deterministic polynomial time algorithm that solves the transportation problem above.
2) Consider the following variation on the problem where we are single truck driver trying to decide which load(s) we can haul. We still have n loads,l1,….ln ,but our truck can carry more than one of them. However, each load has a corresponding weight w1,….wn while our truck is only able to haul a total load of weight at most W. Since we are now the truck driver, we have to decide which loads to haul subject to our weight constraints so that we maximize the amount we charge. Prove or Disprove as before: this variation is NP-complete
Explanation / Answer
Answer:
1. The given problem is a decision problem as we have to decide about the assignment of a truckload l to some truck j. It is also a non-deterministic problem as we have to pick a truck for a given truckload from a set of available trucks (choices). So if this problem can be solved in a polynomial time, it will fall under "Class NP" of problems and can be considered to check for NP-Completeness. But before that we need to prove that it is also a NP-hard problem. If we can prove that the given problem is NP-hard, it will also be NP-Complete provided it belongs to Class NP.
Proof for NP-hard: For NP-hard, a problem L will be termed as NP-hard iff problem of satisfiability reduces to L. To prove that satsifiability reduces to L, we will pick an already known NP-hard problem L' and show that L' reduces to L. Then, by the transitivity property of recucibility, we will prove that L is NP-hard as due to being NP-hard, we already know that satisfiability is reducible to L'
One such known NP-hard problem is 0/1 Knapsack problem. Under this problem, it is to be decided whether a given object having a certain value/cost can be added to a knapsack as a whole or not. For the given problem, we can easily show that an instance of 0/1 Knapsack problem can be reduced to an instance of the given problem i.e. assigning a truckload (object) to a truck (knapsack).
So now, we can say that L' is reducible to L and as satisfiability is already reducible to L'. Hence, from property of transitivity of reducibility, we can establish that satisfiability is reducible to L. Therefore, L i.e. given problem is NP-hard. Now, it is also clear that given problem belongs to Class NP.
Hence, given problem is NP-Complete.
2. This problem can be modelled on the basis of Fractional (classic) Knapsack problem. Classic Knapsack problem is not NP-Compelete. Hence, we can clearly say that given truckload problem is also not NP-Complete. This can be solved by applying a Greedy approach as in case of Knapsack problem. Corresponding algorithm is given below:
---------------------------------------------------
1. Arrange all truckload in the decending order of cost/weight ratio.
2. Then select a truckload with highest cost/weight ratio and add it to truck provided truck capacity allows it and till all applicable options (truckloads) are considered.
3. At the end, an optimal solution will be found.