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
$\begingroup$
$\endgroup$
12
-
12$\begingroup$ because the black box reductions only preserve the YES/NO aspect of the (decision) problems, not the closeness of the approximations. $\endgroup$– Suresh VenkatCommented Jan 9, 2011 at 6:48
-
6$\begingroup$ 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 . $\endgroup$– Suresh VenkatCommented Jan 9, 2011 at 8:45
-
14$\begingroup$ 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. $\endgroup$– Peter ShorCommented Jan 9, 2011 at 14:24
-
5$\begingroup$ 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. $\endgroup$– Suresh VenkatCommented Jan 9, 2011 at 20:12
-
8$\begingroup$ 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. $\endgroup$– Jukka SuomelaCommented Jan 10, 2011 at 14:35
|
Show 7 more comments
1 Answer
$\begingroup$
$\endgroup$
2
Reductions are defined with respect to the decision version of the problems. Approximation ratios for their optimization versions are a separate question, which seems related but doesn't necessarily have to be. So to answer your question with a question, from a philosophical perspective, why should you expect the class NPC to preserve approximation ratios when it isn't defined with respect to them in the first place?
answered Jan 10, 2011 at 13:20
-
$\begingroup$ "Reductions are defined with respect to the decision version of the problems." Is this true for, say Levin reductions? $\endgroup$ Commented Jan 12, 2011 at 4:12
-
$\begingroup$ You're right, not all reductions are defined w.r.t. decision versions, but we can define NPC only in terms of black-box reductions, and then I guess it can lead to debates about how these classes change w/ the reduction used... I should have said "the class NPC is defined for decision problems." It's not really a precise argument, as we could even define a class of decision problems whose optimization versions preserve approximation ratios, but that's not what we do for the class NPC. I guess given @N27's question is a philosophical objection, I'm allowed to give a philosophical response. :) $\endgroup$– Lev Reyzin ♦Commented Jan 12, 2011 at 14:55