Answer:
See explaination
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 \not\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 \not\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}.
