# Why do NP-complete problems not have similar approximation ratios?

Since 2 NP-complete problems are by definition reducible to each other, so a solution to one of them can be obtained by using a black-box solving the other one, why don't they have similar approximation ratios (referring to their optimization counterparts)? I guess that some constant or even polynomial drift might be understood but we have the case of constant-factor approximation algorithms for some NP-complete problems and, on the other hand, other problems that cannot be even approximated by a polynomial-ratio approximation algorithm, such as general TSP? Thank you

• because the black box reductions only preserve the YES/NO aspect of the (decision) problems, not the closeness of the approximations. – Suresh Venkat Jan 9 '11 at 6:48
• if I reduce 3SAT to vertex cover, then vertex cover of size k implies satisfiability and vice versa. But if I get a vertex cover of size 2k, it doesn't mean I can satisfy half the clauses . – Suresh Venkat Jan 9 '11 at 8:45
• Choose a specific reduction from one NP-complete problem to another, and try to extend it to preserve approximation ratios. You'll see what goes wrong. – Peter Shor Jan 9 '11 at 14:24
• Peter's answer is the best one really. Just try it and see what happens. I think by philosophical skepticism you mean 'I don't really get the intuition'. Sometimes the best way is just to try some examples and let the intuition grow. – Suresh Venkat Jan 9 '11 at 20:12
• Yet another way to grow your intuition: Take the vertex cover problem, and change the objective function. Minimise $\log |C|$ vs. $|C|$ vs. $|C|^2$ vs. $2^{|C|}$ over all vertex covers $C$. For each variant, the set of optimal solutions is exactly the same. However, some of the versions are much easier to approximate. The objective function of an optimisation is somewhat arbitrary, and approximability is highly dependent on the choice of the objective function. Indeed, the maximum independent set problem is just the minimum vertex cover problem with a strange objective function. – Jukka Suomela Jan 10 '11 at 14:35