# Does adding a polynomial-time function impact APX-hardness?

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...

• 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)$.
– D.W.
Commented Mar 29, 2023 at 17:15