1
$\begingroup$

I want to show a minimization problem $Y$ has no approximation factor of 1.36. To be more specific the problem $Y$ is the exemplar distance problem between two genomes. Could I reduce from the min vertex cover problem instead of the decision version of the vertex cover problem. The problem I am having with reducing from the decision version is that a vertex cover of size k maps to the $Y$ of size $ \leq ck$, where $c$ is a constant. A decision version for problem $Y$ for me makes no sense, as there will always be a brekpoint distance between two genomes. I tried to research on the internet but I always only find reductions from decision problems. Could we reduce from non-decision problems.

Also when doing reductions from the vertex cover problem. I can't assume the given instance $G,k$ is such that k is the size of the optimal vertex cover right? $k$ is just any size of a Vertex cover.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ What you're talking about is hardness of approximation, it is big topic. So, start with approximation preserving reduction (there are many types of reductions) , then move to see complex technique that used PCP theorem. "see for example Vizirani's textbook and, Williamson and Shmoys's textbook to see examples". See the following lecture to see an overview of techniques in Inapproximabililty By Erik Demaine: youtube.com/watch?v=snugEmWtEm4 $\endgroup$
    – YOUSEFY
    Commented Nov 17, 2019 at 12:52

1 Answer 1

Reset to default
2
$\begingroup$

Yes. See the notion of an approximation-preserving reduction.

Improve this answer
$\endgroup$

Your Answer

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

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