Metric k-center problem (${\min }_{C\subseteq V,|C|\le k}{\max }_{v\in V}{\min }_{c\in C}d(v,c)$)

The metric k-center problem chooses at most $k$ centers from a finite metric space to minimize the largest distance from a point to its nearest center. For $1\le k\le |V|$, exactly $k$ centers gives the same optimum: extra centers never increase the radius. The restriction that centers belong to $V$ matters; allowing centers anywhere in an ambient metric space is a different problem.

The basic packing argument is short. If a radius-$r$ solution uses $k$ centers, its $k$ closed balls cover $V$. Two points assigned to the same center have distance at most $2r$ by the triangle inequality. Thus $k+1$ points with pairwise distances greater than $2r$ certify that no radius-$r$ solution exists. Greedily selecting a new center only outside all existing radius-$2r$ closed balls therefore uses at most $k$ centers whenever a radius-$r$ solution exists, and its final covering radius is at most $2r$. The farthest-first traversal achieves the same approximation ratio without knowing $r$.

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^{\ast }$, two of these points belong to the same optimal radius-$r^{\ast }$ closed ball, so the triangle inequality gives $R\le 2r^{\ast }$. The case $R=0$ is already optimal. This proves a factor-two approximation algorithm.