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