Approximate Algorithms For NP-Complete Problems
I have a question about approximate algorithms for known NP-Complete problems.
I know that if you find an answer for an NP complete problem, that means you can find an answer for any problem that has been reduced to it, but not necessarily for any problem that is has been reduced to. I think that is correct at least.
If you have an algorithm that finds an approximate answer for an NP-Complete problem, does this mean that you can find an approximate answer for all problems that have been reduced to it or problems that it has been reduced to?
For example, Imagine that you constructed an approximation algorithm for the Traveling Salesman Problem that could always calculate a solution that is correct within a factor of 1/k of the optimal tour in O(n ⋅2^k) time. Would you be able to use this approximation algorithm to obtain a “good” solution to all other NP-Complete problems?
I'm thinking no. Proving a problem NP complete with a reduction only ensures that an exact answer correlates to another exact answer. You cannot make the same assumption about an approximate answer.
Even if it is possible, I think it will only give an approximate answer for problems that have been reduced to the TSP, and it will not given an approximate answer for problems that the TSP has been reduced to.
Any thoughts? I really can't convince myself of a correct answer to this question. Thanks in advance!
Re: Approximate Algorithms For NP-Complete Problems
Quote:
Originally Posted by
lesnaubr
If you have an algorithm that finds an approximate answer for an NP-Complete problem, does this mean that you can find an approximate answer for all problems that have been reduced to it or problems that it has been reduced to?
Not generally but there is a class of very hard NP-hard problems (I think it's called MAX SNP) for which no approximation in P exists. If you do find such an approximation then P = NP.
Re: Approximate Algorithms For NP-Complete Problems
Quote:
Originally Posted by
nuzzle
Not generally but there is a class of very hard NP-hard problems (I think it's called MAX SNP) for which no approximation in P exists. If you do find such an approximation then P = NP.
So it sounds like I am correct in assuming that an approximate answer for a certain problem does not guarantee an approximate answer for a problem it has been reduced from or to.
Is there a difference for problems it have been reduced from or problems that it has been reduced to?
Re: Approximate Algorithms For NP-Complete Problems
Quote:
Originally Posted by
lesnaubr
So it sounds like I am correct in assuming that an approximate answer for a certain problem does not guarantee an approximate answer for a problem it has been reduced from or to.
Is there a difference for problems it have been reduced from or problems that it has been reduced to?
I'm not so sure about that. If a problem can be reduced to another problem this indicates both are equally hard so if an approximate solution exists for one it should also exist for the other.
