# Hardness of the k-center problem with relaxed triangle inequality

Consider the $$k$$-center problem where we are given an undirected, complete graph $$G=(V, E)$$, with a distance $$d(u, v) \geq 0$$ for each pair $$u, v \in V$$. Furthermore, we assume that the triangle inequality holds: for each triple $$u, v, w \in V$$ it is the case that $$d(u, w) \leq d(u, v)+d(v+w)$$. The goal is to find $$k$$ clusters, grouping together the vertices that are most similar into clusters together. The goal is to choose a set $$S \subseteq V$$ of $$k$$ cluster centers such that we minimize the maximum distance of a vertex to its cluster center.

It is not difficult to show that there is no $$\rho$$-approximation algorithm for the $$k$$-center problem for $$\rho < 2$$ unless $$\mathbf{P}=\mathbf{NP}$$: Consider the dominating set problem, which is NP-complete. In the dominating set problem, we are given a graph $$G = (V, E)$$ and an integer $$k$$, and we must decide if there exists a set $$S ⊆ V$$ of size $$k$$ such that each vertex is either in $$S$$, or adjacent to a vertex in $$S$$. Given the instance $$G=(V, E)$$ of the dominating set problem, we can then construct an instance $$G'=(V, E')$$ of the $$k$$-center problem by setting the distance between adjacent vertices in $$G$$ to 1 in $$G'$$, and the distances between nonadjacent vertices in $$G$$ to 2 in $$G'$$. Then, there is a dominating set of size $$k$$ if and only if the optimal distance ($$OPT$$) for $$k$$-cluster instance $$G'$$ is $$1$$. Thus, if we assume we have an approximation algorithm $$A$$ for the $$k$$-center problem with approximation factor $$\rho < 2$$, we can run it on $$G'$$. Then, if $$OPT=1$$, $$A$$ will return a solution with distance $$<2$$, i.e. 1. Else, if $$OPT =2$$, $$A$$ will return a solution with distance at least $$2$$. Thus, we can solve the dominating set decision problem, which implies that $$\mathbf{P}=\mathbf{NP}$$.

My question is then concerned with the $$c$$-relaxed $$k$$-center problem, where we do not have a metric but only the following approximate triangle inequality: For each triple $$u, v, w \in V$$, it is the case that $$d(u, w)/c \leq d(u, v)+d(v, w)$$. Is it possible to show that unless $$\mathbf{P}=\mathbf{NP}$$, there is no solution to the $$c$$-relaxed $$k$$-center problem with approximation factor $$\rho < c+1$$

You can show hardness of approximation of any $$\rho < 2c$$.
Simply take the distance between non-adjacent vertices to be $$2c$$ and distance between the adjacent vertices to be $$1$$. Note that the graph should satisfy relaxed triangle-inequality, and it indeed does, given that $$c \geq 1$$.