December 13th, 2011, 11:25 PM
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!
Tags for this Thread
Click Here to Expand Forum to Full Width