Please you can not solve it do not spam and write ... you can skip it if you do not

Suppose that there is a graph G = (V, E) where the vertices can be of two types: there is a set A of possible antennae locations and a set S of cities, with V = AU S. The graph is complete, i.e. for any pair {x, y} CV we also have that (x, y) E. Moreover, the weight of each each edge (x, y) is given by the distance function d : V2 + R; it satisfies the properties d(x, y) = d(y,x) > 0, d(x,x) = 0 and d(x,z) + d(z,y) > d(x, y), for all x, y, z V. Our goal, is to select k antennae such that the maximum distance from a city to any chosen antenna is minimized. Specifically, we need to find a U C A such that |U|= k and max min d(x,y) TES JCU is minimized. 1. Show that minimizing this objective is NP-hard. 2. Find a 3-approximation algorithm. 3. Show that finding an a-approximation with a 0, d(x,x) = 0 and d(x,z) + d(z,y) > d(x, y), for all x, y, z V. Our goal, is to select k antennae such that the maximum distance from a city to any chosen antenna is minimized. Specifically, we need to find a U C A such that |U|= k and max min d(x,y) TES JCU is minimized. 1. Show that minimizing this objective is NP-hard. 2. Find a 3-approximation algorithm. 3. Show that finding an a-approximation with a