Say we have a constant approximation algorithm for the following objective: $$\min_x f(x) \;\;\;\;\;\; (1)$$
Now, we want to solve the following objective:
$$ \max_x (N - f(x)) \;\;\;\;\;\; (2) $$
where $N> f(x)$ for all $x$.
Notice that the optimal is the same for both equations, i.e. $x^*=\arg\min_x f(x)= \arg\max_x (N - f(x))$.
But if there is an $\alpha$-approximation scheme for (1) it doesn't implies there is one for (2). Formally, Let $x^\alpha$, s.t $\frac{f(x^\alpha)}{f(x^*)} \leq \alpha$. Then, in not true that $\frac{N- f(x^*)}{N-f(x^\alpha)}\leq \alpha$
Example: Consider $\alpha=2, f(x^*) = 1, f(x^\alpha) =2$. Then if $N=2.5$, $\frac{N- f(x^*)}{N-f(x^\alpha)}= 3 > \alpha$
I have two questions in this setting:
- If there is an $\alpha$-approximation scheme for (2) can we construct one for (1)?
- Does there exists an $\alpha$-approximation scheme for (2)?