COMPUTER SCIENCE TRIPOS Part II – 2017 – Paper 9
Advanced Algorithms (TMS)
(a) Give two examples of greedy algorithms and state their approximation ratios.
[4 marks]
(b) Consider the Centre Selection Problem, defined as follows. The input consists
of n points p1, p2, . . . , pn in a metric space, and an integer k > 0. The goal is
to find k centres C = {c1, c2, . . . , ck} (not necessarily from among the n points)
so that r(C) = max1≤i≤n dist(pi
, C), where dist(pi
, C) = min1≤j≤k dist(pi
, cj ), is
minimised.
(i) Consider the standard greedy approach: solve the problem optimally for
k = 1 and then extend the solution to larger values of k by adding the
optimal point to the current solution. Why is this likely to give a poor
result? [4 marks]
(ii) Consider the following algorithm to solve the Centre Selection Problem:
Let C be the empty set
Repeat k times
Select a point p_i with maximum distance dist(p_i,C)
Add point p_i to the set C
Return C
Derive a lower bound for this algorithm on the minimum pairwise distance
among the chosen centres C. [4 marks]
(iii) Give an upper bound, as tight as possible, on the approximation ratio of
the algorithm in part (b)(ii). [2 marks]
(iv) Give a detailed analysis in order to justify your answer for part (b)(iii).
Hint: Exploit the lower bound derived in part (b)(ii) in order to construct
disjoint balls around the centre points. [6 marks]