Optimization problems with same optimal value, but different approximation behavior

Question

Context: related to this answer.

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.

Answer 1

What about something like minimum vertex cover vs. minimum fractional vertex cover (i.e., optimal solution of the LP relaxation of the vertex cover problem) in bipartite graphs?

These two problems have the same optimal value.

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