0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Revisiting the course material should give you an idea about where to start. Then flesh out your question. $\endgroup$ – Raphael Apr 13 '16 at 0:11
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.