For this problem were trying to rank items according to particular criteria. Say were trying to rank automobiles perhaps we have measures of criteria like gas mileage, safety rating, etc. and we want to know what automobiles are better than other automobiles in every criteria (assume we all have the same opinion of whats good: high gas mileage, safe, etc). More formally, suppose we have k criteria for items x and y denoted by x1, x2, . . . , x k and y1, y2, . . . , yk. We will say x dominates y if x1> y1 and x2> y2and. . . , xk> yk.

(a) Show the dominating relationship is transitive.

(b) Assume you are given n items I1, I2, . . . , In and your job is to find the longest sequence [Is1, Is2, . . . , Ism] of items such that Isj dominates Isj+1 for all j= 1,2, . . . , m?1. Show how to phrase this as a graph problem,explain what to do to the graph to solve this problem, and express the running time of your algorithm in terms of n and k.

(c) A Pareto optimal set of items would be those that are not dominated by any other items. Show how to find a Pareto optimal set of then items from the graph you built.