= Metric k-center problem
{title2=$\min_{C\subseteq V,\,|C|\leq 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\leq k\leq|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$.
Back to article page
