Question

Given an integer k, a set C of n cities c1, . . . , cn, and the distances between these cities dij = d(ci , cj ), for 1 ⤠i < j ⤠n, where d is the standard Euclidean distance. We want to select a set H of k cities for building mobile hospitals in light of the coronavirus outbreak. The distance between a given city c and the set H is given by d(c, H) = minhâH d(c, h). The goal is to select a set H of k cities that minimizes r = maxcâC d(c, H). Namely, the maximum distance from a city to the nearest mobile hospital is minimized. Give a 2-approximation algorithm for this problem.

Answer 1

See explaination

Step-by-step explanation:

2-Approximation Algorithm

Step 1: Choose any one city from the given set of cities C arbitrarily and put it in to a set H which is initially empty.

Step 2: For every city c in set C that is currently not present in set H compute min_distc = Minimum[ d(c, c1), d(c, c2), d(c, c3), ..... . . . . d(c, ci) ]

where c1, c2, ... ci are the cities in set H

and d(x, y) is the euclidean distance between city x and city y

Step 3: H = H ∪ {cx} where cx is the city have maximum value of min_dist over all possible cities c, computed in Step-2.

Step 4: Step-2 and Step-3 are iterated for k-1 times so that k cities are included int set H.

The set H is the required set of cities.

Example

Assume:-

C = {0, 1, 2, 3}

d(0,1) = 10, d(0,2) = 7, d(0,3) = 6, d(1,2) = 8, d(1,3) = 5, d(2,3) = 12

k = 3

Solution:-

Initially H = { }

Step-1: H = {0}

Step-2: Cities c \\ot\in H are {1, 2, 3}

min_dist1 = min{dist(0,1)} = min{10} = 10

min_dist2 = min{dist(0,2)} = min{7} = 7

min_dist3 = min{dist(0,3)} = min{6} = 6

Step-3: Max{10, 7, 6} = 10

Step-4: cx = 1

Step-5: H = H ∪ cx = {0} \cup {1} = {0, 1}

Step-6: Cities c \\ot\in H are {2, 3}

min_dist2 = min{dist(0,2), dist(1,2)} = min{7, 8} = 7

min_dist3 = min{dist(0,3), dist(1,3)} = min{6, 5} = 5

Step-7: Max{7, 5} = 7

Step-8: cx = 2

Step-9: H = H \cup cx = {0, 1} \cup {2} = {0, 1, 2}

Result: The set H is {0, 1, 2}.