# Proof of approximation ratio for approximate triangle inequality version of k-center

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