# Approximation factor preserving reduction

The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365:

Let $$\Pi_1$$ and $$\Pi_2$$ be two minimization problems, an approximation factor preserving reduction from $$\Pi_1$$ to $$\Pi_2$$ consists of two polynomial-time algorithms, $$f$$ and $$g$$, such that:

• for any instance $$I_1$$ of $$\Pi_1$$, $$I_2 = f(I_1)$$ is an instance of $$\Pi_2$$ such that $$OPT_{\Pi_2}(I_2) \leq OPT_{\Pi_1}(I_1)$$.
• for any solution $$t$$ of $$I_2$$ (constructed above), $$s = g(I_1, t)$$ is a solution of $$I_1$$ such that: $$obj_{\Pi_1}(I_1, s) \leq obj_{\Pi_2}(I_2, t)$$.

It is clear that this reduction preserves the approximation factor.

QUESTION: Since any solution of $$I_2$$ shall have an objective value no less than that the objective value of the corresponding solution of $$I_1$$, if the solution $$t$$ to $$I_2$$ is optimal, that is, $$obj_{\Pi_2}(I_2, t) = OPT_{\Pi_2}(I_2)$$, doesn't this imply that equality should always be satisfied on the first condition? In other words, $$OPT_{\Pi_2}(I_2)$$ can never be less than $$OPT_{\Pi_1}(I_1)$$, or else, some solution of $$I_1$$ will have an objective value less than its optimal (which yields a contradiction for a minimization problem).

I understand that we are mainly interested in optimization problems that are NP-hard, however, in this reduction, we did not specify that the solution of $$I_2$$ should not be optimal.

In this book, the author gives several such reductions between different problems, however, none of those reductions were built upon the strict equality of the first condition.

• I think my confusion raises from the inaccurate definition of this reduction(no doubt this book is one of the greatest books on approximation algorithm). By my preliminary thought, any two problems (vertex cover to feedback vertex set, Steiner tree to metric Steiner tree, etc) that are reducible under this reduction must have $OPT_{\Pi_1} = OPT_{\Pi_2}$. Aug 14, 2020 at 13:55