Skip to main content
edited tags
Link
added 117 characters in body; added 13 characters in body
Source Link
N27
  • 573
  • 6
  • 15

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)? Why certainI 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 admit even constant ratio approximation schemes while othersand, on the other hand, other problems that cannot even be even approximated by a polynomial-factorratio approximation algorithm, such as general TSP? Thank you

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)? Why certain NP-complete problems admit even constant ratio approximation schemes while others cannot even be approximated by a polynomial-factor algorithm, such as general TSP? Thank you

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

Source Link
N27
  • 573
  • 6
  • 15

Why do NP-complete problems not have similar approximation ratios?

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)? Why certain NP-complete problems admit even constant ratio approximation schemes while others cannot even be approximated by a polynomial-factor algorithm, such as general TSP? Thank you