snippetMinor
How to find an example for a case in the metric k-center problem
Viewed 0 times
caseproblemthehowexamplemetriccenterforfind
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#164828, answer score: 4
Revisions (0)
No revisions yet.