= Farthest-first traversal
{wiki}
Starting with an arbitrary <point> in a finite <metric space>, repeatedly select a <point> maximizing its distance to the selected <set>. Maintain each <point>'s distance to its nearest selected center; each new center updates all those distances, giving $O(k|V|)$ distance evaluations for $k$ centers.
For the <metric k-center problem>, let $R$ be the final covering radius and add a <point> realizing $R$ to the $k$ selected centers. Every pair among these $k+1$ <points> has distance at least $R$: at each selection the current maximum distance is at least its final value. If the optimum radius is $r^*$, two of these <points> belong to the same optimal radius-$r^*$ <closed ball>, so the <triangle inequality> gives $R\leq2r^*$. The case $R=0$ is already optimal. This proves a factor-two <approximation algorithm>.
Back to article page
