Question 4: Finding diverse elements . ...... [12] A common problem in returning search results is to display results that are diverse. A simplified formulation of the problem is as follows. We have n points in Euclidean space of d-dimensions, and suppose that by distance, we mean the Manhattan distance (or SLC distance!) between points. The goal is to pick a subset of k (out of the n) points, so as to maximize the sum of the pairwise distances between the chosen points. Le., if the points are denoted P = {p1, p2, . ..;Pn), then we wish to choose an S C P, such that [S| = k, and Cpap,es d(pi; p;) is maximized. A common heuristic for this problem is local search. Start with some subset of the points, call them S = {q1, 92, ...; qk} C P. At each step, we check if replacing one of the q; with a point in P\\ S improves the objective value (the \\ operator denotes set subtraction). If so, we perform the swap, and continue doing so as long as the objective improves. The procedure stops when no improvement (of this form) is possible. Suppose the algorithm ends with S = (91, ...; qx}. We wish to compare the objective value of this solution with the optimum one. Let {71, 12, ..., Tx} be the optimum subset. (a) [3] Use local optimality to argue that: k k 1=2 1=2 (b) [4] Use inequalities of the form above, deduce that: k (k - 1) . d(x1, 12) d(q1, qr) 7= 2 (c) [5] Use this result to argue that the local optimum solution is not worse than half of the global optimum, i.e. the objective value of local optimum is at least 1/2 the true optimum