Consider the problem of scheduling n jobs with processing times p1pn on m identical machines to minimize completion time. We know that the greedy (list scheduling) algorithm is a (4/3)(1/3m) approximation algorithm. The proof of this result contains a detailed case analysis. This problem is about giving a much simpler proof of a weaker result. Show that the same algorithm is a 3/2-approximation algorithm. Start with proving the following claim. Let us assume that job j finishes last and its machine has at least two jobs. Then jm+1 and pjpm+1OPT/2