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.

  • 5
    $\begingroup$ Can you be more specific: what exactly don't you understand? Other than that, I think this would be a good question for CS.SE after some editing. $\endgroup$ – Juho Jun 21 '12 at 8:06
  • 1
    $\begingroup$ Welcome to CSTheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. As stated by @mrm, you should try posting it on Computer Science. $\endgroup$ – Gopi Jun 21 '12 at 12:47

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

  • 4
    $\begingroup$ There is a policy on this site of not answering non-research-level questions, there has been many discussion on meta about this. It is better to flag this question and wait until a moderator moves it to cs.SE before answering it. $\endgroup$ – Gopi Jun 21 '12 at 12:43
  • $\begingroup$ @Gopi Sorry, I was unaware of this. I'll be more careful in the future. Thanks for the info! $\endgroup$ – Juho Jun 21 '12 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.