Suppose that there is a graph G = (V, E) where the vertices can be of...

 

Transcribed Image Text:

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 UC A such that |U| = k and max min d(x, y) xS yU 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 < 3 is also NP-hard. If you do this, there is no need to include an answer to the first sub-question. 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 UC A such that |U| = k and max min d(x, y) xS yU 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 < 3 is also NP-hard. If you do this, there is no need to include an answer to the first sub-question.

Answer rating: 100% (QA)

1 To show that minimizing the objective of selecting k antennae such that the maximum distance from a city to any chosen antenna is minimized is NPhar... View the full answer