3
$\begingroup$

Let us say that I have a problem $P(n)$ that I need to solve (where $n$ is the size of the input of problem $P$). I used a polynomial-time reduction from a known NP-hard problem $Q(m)$ (where $m$ is the size of the input of problem $Q$) to $P(n)$ and showed that $P(n)$ is NP-hard. The time complexity of the reduction is $O(n^k)$ for some fixed $k$.

Can I use a known approximation algorithm for problem $Q(m)$ that is $O(f(m))$-approximation for problem $Q(m)$ to design an approximation algorithm for problem $P(n)$ that is $O(g(n))$-approximation for problem $P(n)$?

$\endgroup$
  • $\begingroup$ Yes, if your reduction is approximation-preserving. $\endgroup$ – Yuval Filmus Jan 26 '16 at 21:22
  • $\begingroup$ What are your thoughts? Have you tried to prove that the answer is yes? If so, where did you get stuck? $\endgroup$ – D.W. Jan 26 '16 at 22:57
  • $\begingroup$ Thank you for your thanks. For your information, comments are transitory and can be deleted at any time (e.g., when they've served their purpose, or if they are not aimed at improving the post or requesting clarification or providing additional information, roughly speaking). See cs.stackexchange.com/help/privileges/comment: "Comments are temporary "Post-It" notes" and see "When should I comment?". $\endgroup$ – D.W. Jan 27 '16 at 17:28
4
$\begingroup$

Yes, but you need an approximation-preserving reduction in the opposite direction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.