Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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$.
