2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.