Approximation Algorithm:

1. (**) Recall that the input to the k-center problem is a set V of points in a metric space where we are given the distance dij between any pair of points, i and j. Consider the following local search algorithm for the k-center problem. Assume that the algorithm knows the optimum, OPT. The algorithm starts with an arbitrary set S S V of k points. Let N(S) denote the number of points that are within distance 20PT, from S, ie. N(S) :( V | d(u, S) 20PT}|Note that as usual, d(v, S) := minues du,u. In each iteration, it finds a vertex iE S and j such that N(SV) U {j)) N(S), if such a pair exits. The algorithm terminates if can't find such a pair, and returns S as the solution. Is this algorithm a 2-approximation? If so, prove it. Otherwise, give a counter example