CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4
  1. #1
    Join Date
    Jan 2009
    Posts
    5

    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!

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Approximate Algorithms For NP-Complete Problems

    Quote Originally Posted by lesnaubr View Post
    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.

  3. #3
    Join Date
    Jan 2009
    Posts
    5

    Re: Approximate Algorithms For NP-Complete Problems

    Quote Originally Posted by nuzzle View Post
    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?

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: Approximate Algorithms For NP-Complete Problems

    Quote Originally Posted by lesnaubr View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured