For example, for the $k$-center problem we want to prove that a 2-approximation algorithm is optimal.A proof is presented on page 39 (Theorem 2.4) in Williamson and Shmoys, The Design of Approximation Algorithms. In the proof, by taking dominating set problem we get a special case of $k$-center problem.I don't get the part from here.
What is meant by if there exists a $\rho$-approximation algorithm with $\rho < 2$, then P = NP?
cc.complexity theory;np hardness;approximation algorithms;approximation hardness
Here's the same proof in other words. The idea is that if we had a $(2-\epsilon)$-approximation algorithm with $\epsilon > 0$, we could decide whether or not there is a dominating set of size $k$. In other words, we want to show that there is no $(2-\epsilon)$-approximation algorithm with $\epsilon > 0$ for $k$-center unless $\mathsf{P} = \mathsf{NP}$. Recall that the dominating set problem is indeed $\mathsf{NP}$-complete.Let $G = (V,E)$ with integer $k$ be an instance of the dominating set problem. Let us then define a complete graph $G'$ such that the distance between adjacent vertices is 1 while nonadjacent vertices have a distance of 2. $G'$ satisfies the triangle inequality as well.Suppose $G$ has a dominating set of size at most $k$. Then, $G'$ has a $k$-center cost of 1. Now, a $(2-\epsilon)$-approximation algorithm gives us a solution with cost $< 2$. If there is no such dominating set in $G$, every $k$-center has cost $\geq 2 > 2-\epsilon$. Thus, a $(2-\epsilon)$-approximation algorithm for the $k$-center problem can decide whether or not there is a dominating set of size $k$.