3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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}$. $\endgroup$
    – Null_Space
    Aug 14 '20 at 13:55
0
$\begingroup$

That looks right. The only exception I can think of is problems where there isn't an optimal solution, but just a sequence of ever-better solutions converging to, but never attaining, some optimum. Though actually, even then, if the optima weren't the same, it should be possible to find some solution in between the optima, which would arrive at a contradiction. So it seems what you say should still hold, unless I'm also missing something.

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