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 standard Euclidean distance. 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. I.e., if the points are denoted P = {p1, p2, . . . , pn}, then we wish to choose an S P, such that |S| = k, and P pi,pjS d(pi , pj ) is maximized. A common heuristic for this problem is local search. Start with some subset of the points, call them S = {q1, q2, . . . , qk} P. At each step, we check if replacing one of the qi with a point in P \S improves the objective value. 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 = {q1, . . . , qk}. We