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

<p>These two problems have the same optimal value.</p>

<p>However, if I give you a black-box algorithm that finds a <span class="math-container">$(1+\epsilon)$</span>-approximation of the minimum <em>fractional</em> vertex cover, this does not help much if you would like to output a <span class="math-container">$(1+\epsilon)$</span>-approximation of the minimum vertex cover.</p>

<p>This can be formalized in some sufficiently weak models of computation. For example, if we look at distributed algorithms, one can show that a <span class="math-container">$(1+\epsilon)$</span>-approximation of the minimum fractional vertex cover is easy to find, while a <span class="math-container">$(1+\epsilon)$</span>-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 <span class="math-container">$\epsilon &gt; 0$</span> 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.)</p>

CC BY-SA 4.0
2020-03-15T12:00:15.417Z
2020-03-15T12:00:15.417Z
Jukka Suomela
<p>Context: related to <a href="https://cstheory.stackexchange.com/a/46394/47855">this answer</a>.</p>

<p>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?</p>

<p><strong>Are there two minimization problems with same optimal value, but different behavior with respect to approximation?</strong></p>

<p>Existence of such a pair of problems justifies the definition of approximation factor preserving reduction.</p>

CC BY-SA 4.0
2020-03-15T04:36:32.207Z
See the linked answer for definition of approximation factor preserving reduction
Cyriac Antony
<approximation-hardness><approximation>
Optimization problems with same optimal value, but different approximation behavior
Cyriac Antony
# Optimization problems with same optimal value, but different approximation behavior

(Asked by: username_0 on 2020-03-15)

Context: related to [this answer](https://cstheory.stackexchange.com/a/46394/47855).

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.

**Tags:** approximation-hardness, approximation
> **Comments:**
> **username_0**: See the linked answer for definition of approximation factor preserving reduction  

---

## 1 answers

### Answer by username_1 on 2020-03-15. Score: 4 | Accepted answer

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


---

