 Metric k-center problem

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