Consider the standard $k$-center problem i.e find $k$ disks of radius $r$ that cover all points in a point set $P$. This problem has a well known greedy 2-approximation algorithm where you (essentially) choose points from $P$ as the centers of each of the $k$ disks and each time you pick a point you pick the one that maximizes the distance from the one chosen just prior (see details here).

My slight variation of this is more formally described as follows; Given a set of points $P$ with a distance between two points $i,j \in P$ as $d_{ij} \geq 0$ and by convention $d_{ii} = 0$. The triangle inequality does not quite hold, but we know that for any triple of points $i,k,j \in P$ we have that $d_{ik} + d_{kj} \geq d_{ij}/c$ for some positive constant $c$ - call this the approximate triangle inequality. Let $S\subseteq P,|S|=k$ be our center clusters. Let $d(i, S) = \min_{j\in S} d_{ij}$ i.e the closest cluster center to point $i$ hence the radius of $S$ is $\max_{i\in P} d(i, S)$. The goal is thus to find a set $S$ of size $k$ of minimum radius. Employing the same greedy algorithm, in this case, would yield what approximation factor?

Attempted proof for the approximation factor so far: If we look at an optimal solution $S^*$ with optimal radius $r^*$ (this solution partitions the points into $k$ clusters $C_1, C_2, ..., C_k$), any two points in the same cluster can not be more than $2r^* / c$ apart by the approximate triangle inequality. Now consider $S \subseteq P$ as chosen by the greedy algorithm. We have two cases: (i) if $S$ is chosen such that each points is from a different cluster from the optimal solution $S^*$ then any point $p \in P$ is at most $2r^* / c$ from every point in $S$. (ii) if we chose two points from the same of cluster relative to the optimal solution then we know that we only chose that second point from a cluster because it was the furthest from any of the nodes in $S$ which is at most $2r^* / c$, hence the approximation factor is $2/c$.

However this approximation factor doesn't really makes sense to me (it would yield a shorter radius than the optimal one if c > 2).


You are doing everything correctly. You are just making a typo: any two points in the same cluster are at most $2c \cdot r^{*}$ distance apart. Therefore, the approximation guarantee would be $2c$.


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.