# Optimization problems with same optimal value, but different approximation behavior

I would like to see an example to emphasize that approximation behavior depends not only on the optimal value but also the set of solutions. This makes sense logically. If two problems are duals of each other, then they have the same optimal value but can have different behavior with respect to approximation (eg: independent set and vertex cover). But, is the same possible if both are minimization problems, or both are maximization problems?

Are there two minimization problems with same optimal value, but different behavior with respect to approximation?

Existence of such a pair of problems justifies the definition of approximation factor preserving reduction.

• See the linked answer for definition of approximation factor preserving reduction – Cyriac Antony Mar 15 at 4:36

However, if I give you a black-box algorithm that finds a $$(1+\epsilon)$$-approximation of the minimum fractional vertex cover, this does not help much if you would like to output a $$(1+\epsilon)$$-approximation of the minimum vertex cover.
This can be formalized in some sufficiently weak models of computation. For example, if we look at distributed algorithms, one can show that a $$(1+\epsilon)$$-approximation of the minimum fractional vertex cover is easy to find, while a $$(1+\epsilon)$$-approximation of the minimum vertex cover is hard to find in bipartite graphs. (Here "easy" is e.g. constant time in the LOCAL model and "hard" is e.g. at least logarithmic time in the same model, assuming a sufficiently small constant $$\epsilon > 0$$ and some constant upper bound on the maximum degree. So there cannot be e.g. constant-time approximation-preserving LOCAL model reductions between the two problems, even if the optimum is the same.)