
December 13th, 2011, 10:25 PM
#1
Approximate Algorithms For NPComplete Problems
I have a question about approximate algorithms for known NPComplete 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 NPComplete 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 NPComplete 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!

December 13th, 2011, 11:48 PM
#2
Re: Approximate Algorithms For NPComplete Problems
Originally Posted by lesnaubr
If you have an algorithm that finds an approximate answer for an NPComplete 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 NPhard 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.

December 14th, 2011, 09:53 AM
#3
Re: Approximate Algorithms For NPComplete Problems
Originally Posted by nuzzle
Not generally but there is a class of very hard NPhard 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?

December 15th, 2011, 12:50 AM
#4
Re: Approximate Algorithms For NPComplete Problems
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.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
