Question

4. One ordered pair u (V1,U2) dominates another ordered pair u-(ui,u2) iful > ข1 and U2 > Un Given a set S of ordered pairs, an ordered pair u E S is called Pareto optimal for S if there is no vES such that v dominates u. Give an efficient algorithm that takes as input a list of n ordered pairs and outputs the subset of all Pareto-optimal pairs in S. (10 points correct reasonably fast algorithm with justification, 5 points efficiency and time analysis). (Optional. Solve this problem with vectors of size 3, where u-ul,V2, t's) dominates u-ui, u2.w

Answer 1

Problem is interesting . We have to first understand that the domination relation is partial order relation which means it satisfies reflexive, antisymmetric and transitive property.

Now if we represent the set S as a directed graph G=(V,E) where |S|=|V| I.e. we represent every ordered pair u by vertex u and there will be an edge (u,v) in E if v dominates u.

Now note that an ordered pair u will be pareto optimal if there is no outgoing edge from vertex u because if an edge (u,v) exist then u cannot be pareto optimal.

Hence our algorithm will first create a directed graph G=(V,E) as per above mentioned rule and then we will find those vertices which does not have any outgoing edge.

We will create graph G =(V,E) represented as adjacency list.

ALGORITHM(SET S)

1. For every ordered pair v in S:-

2.......Create a vertex v

3. For every ordered pair u in S:-

4. ..........For every ordered pair v !=u in S:-

5................. if v dominates u

6........................Then add v in adjacency list of u

//Now we select vertices whose adjacency list of neighbours is EMPTY

7. For every vertex v in V:-

8..........If adjacency list of v is empty

9...............Then Solution.Add(v) //Add this ordered pair in solution

10. Return Solution

Above algorithm takes O(V²) time where size of V is same as size of S .

Please comment for any clarification.