I have two optimization problems $A$ and $B$, and I recently managed to show that there exist functions $f$ and $g$ that are computable in polynomial time, such that for any instance $x$ of $A$ there holds $$OPT_A(x) + g(x) = OPT_B(f(x)).$$

I know that $A$ is NP-hard, which implies that $B$ must be NP-hard as well. However, how about APX-hardness? Can I say anything about the (in)approximability of $B$ assuming that $A$ is APX-hard, or does the $+g(x)$ mess everything up, and nothing can be concluded?

I don't have a very good intuition for approximability-preserving reductions, so I tried to prove it by arguing that, if there were an approximation algorithm for $B$ with arbitrarily small ratio $C$, then there must also be one for $A$; this would contradict the APX-hardness of $A$, and thus $B$ must be APX-hard. However, the presence of this $+g(x)$ invalidates this argument, and I'm not sure how to get around that...

  • $\begingroup$ I doubt it. Consider a case where $g(x)$ is always/often/sometimes much larger than $OPT_B(f(x))$. Then an approximation ratio for $OPT_B(f(x))$ doesn't translate into any useful approximation ratio for $OPT_A(x)$. $\endgroup$
    – D.W.
    Commented Mar 29, 2023 at 17:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.