5
$\begingroup$

Given $n$ points in a 2d metric space, the $k$-center problem asks us to find a subset of size $k$ of the points which we will call centers. The task is to pick these centers to minimize the maximum distance from any point to its closest center.

A classic greedy algorithm repeatedly picks points which are furthest from any existing center until $k$ have been chosen and adds them to the set of centers.

An analysis of this $2$-approximation algorithm has two cases that relate the chosen centers to those from an optimal solution. One of those two cases is when two chosen centers are closest to the same center in an optimal $k$-center solution. But how can this ever occur? Is there a concrete example to show this occurring?

$\endgroup$
1
  • $\begingroup$ I think you can simply say metric space, instead of "2d metric space". $\endgroup$ Commented Jan 3 at 21:03

2 Answers 2

4
$\begingroup$

The following is a simple example:

Consider six points on a line: $p_1, \dotsc, p_6$. Let $k = 2$. The points $p_4, p_5, p_6$ are at the same position (or you can consider them very close to each other).

Then, there is an optimal solution $\{p_2, p_5\}$ with cost $2$.

Suppose, the greedy algorithm chooses the first center as $p_3$. Then, the next chosen center will be $p_1$, which is from the same optimal cluster. And, the cost of the greedy solution is $d(p_3, p_4) \approx 4 = 2 \cdot OPT$.

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ This is a very nice example. Thank you. $\endgroup$
    – Simd
    Commented Jan 4 at 8:23
4
$\begingroup$

Take five equidistant points, $p_1, ..., p_5$ on a line and let $k=2$. The optimal solution picks points $p_2$ and $p_4$ with quality $\text{OPT}=d$.

Now, suppose the arbitrarily chosen center is point $p_3$, the central point. The next point will (wlog) be $p_1$. The quality of this solution is $\text{dist}(p_3, p_5) = 2d$.

$\endgroup$
5
  • $\begingroup$ How many points are there in your setup? $\endgroup$
    – Simd
    Commented Jan 3 at 21:22
  • $\begingroup$ This is answering a different question. I want, in your example, $p_3$ and $p_1$ to have the same optimal point as as their closest neighbor. But in your example $p_2$ and $p_4$ are equally close to $p_3$ so it doesn’t quite work. $\endgroup$
    – Simd
    Commented Jan 4 at 6:57
  • $\begingroup$ $p_1$ and $p_3$ are both closest to $p_2$, which you can also force unique if you move $p_4$ just $\epsilon$ to the right. $\endgroup$ Commented Jan 4 at 7:47
  • $\begingroup$ You ask: "two chosen centers are closest to the same center in an optimal $k$-center solution". $p_1$ and $p_3$ (chosen centers) are closest to the same center ($p_2$) in an optimal solution. Isn't this what you ask? $\endgroup$ Commented Jan 4 at 7:48
  • $\begingroup$ Isn’t $p_3$ equidistant to $p_2$ and $p_4$? $\endgroup$
    – Simd
    Commented Jan 4 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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