Showing that an algorithm is 2-approximation

Question

I'm having trouble showing that this algorithm is 2-approx.

We are given a set P of n points on the plane, and a positive integer k. We want to partition these points into k sets such that the largest distance between any two points which belong to the same part is minimized. Show that the following is a 2-factor approximation algorithm.

Set S = ∅.

For i = 1, . . . , k do

Select the farthest point from S and add it to S.

EndFor

Put each point p ∈ P in the same part as the closest point in S to p.

I honestly don't know where to start. I can see that after each iteration, the distance between any point in P and the points in S become smaller. But after that I can't really see any good observations.

• Raphael: Revisiting the course material should give you an idea about where to start. Then flesh out your question.

Answer 1

The place to start is at the simplest case: $k = 2$. Suppose that the points in $S$ are $x,y$. Consider some optimal solution of value 1ドル$. We consider two cases.

• $x,y$ belong to the same cluster. Thus $d(x,y) \leq 1$. Since $y$ is the farthest point from $x,ドル all other points are at distance at most 1ドル$ from $x,ドル and in particular at distance at most 1ドル$ from $\{x,y\}$. This means that in the clusters generated by the algorithm, each point is at distance at most 1ドル$ from its base (either $x$ or $y$), and so the diameter of each cluster is at most 2ドル$.

• $x,y$ belong to different clusters. In this case, since the optimal solution has value 1ドル,ドル each point other than $x,y$ is within distance 1ドル$ of either $x$ or $y$ (the one which shares cluster with it). This means that in the clusters generated by the algorithm, each point is at distance at most 1ドル$ from its base, and so again the diameter of each cluster is at most 2ドル$.

See if you can generalize these ideas for $k > 2$.