k-center problem: proof for Gon algorithm gives a 2-approximation

Question

The $k$-center problem is where we a given a graph $G(V,E)$, an integer $k$, a distance metric $d$ and we want to find a subset $C\subseteq V$ (such that $|C|\leq k$) which minimizes the following function: $\max_{v\in V}\min_{c\in C}d(v,c)$.

I am trying to understand the proof that the $Gon$ algorithm is a 2-approximation. The algorithm arbitrarily selects the initial center and loops for $k-1$ iterations, where at each iteration it adds the vertex which is furthest away from its nearest center as a new center.

The full proof that this algorithm gives a 2-approximation is described in Gonzalez, Clustering to minimize the maximum intercluster distance. The cost of the optimal solution is $OPT(V)$ and they describe the term "$(k+1)$-clique of weight $h$ for $V$":

Set $T$ is said to form a $(k+1)$-clique of weight $h$ if the cardinality of set $T$ is $k + 1$ and every pair of distinct elements in $T$ are at least $h$ units apart.

The part that I don't understand is the following lemma:

Lemma 2.1: If there is a $(k+1)$-clique of weight $h$ for $S$, then $OPT(V)\geq h$.

My question is, what is the proof for this lemma?

Answer 1

If $k+1$ vertices are at least $h$ units apart, then no ball of diameter $< h$ can cover two of these vertices, hence you would need at least $k+1$ balls.

Since you want to have at most $k$ balls, $h$ must be at least the minimum distance of the $k+1$ vertices (pairwise).

Another way of phrasing it would be:

If you have a set $T$ of $k+1$ points, and at most $k$ balls of diameter $h$, then at least one ball must contain two points. Let $d$ be the shortest distance between two vertices in $T$ (the two closest vertices). Then $h \geq d$.

---

Taking the contra-positive of the lemma: If $\text{OPT} < h$, then you cannot have $k+1$ points that have pairwise distance $\geq h$, or in other words, if $\text{OPT} < h$ then

1. Any set with pairwise distance at least $h$ has at most $k$ vertices
2. Any set with at least $k+1$ vertices has a pair with distance less than $h$.