Do there exist two equivalent objective functions one of which can be approximated but another one cannot? I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below are the definitions.
Problem A: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$ each of which is not greater than the corresponding weight (i.e., $0&lt;v_h\leq w_h$ ($1 \leq h \leq i$)), and a bag with capacity $B=\sum_h v_h$, we want to insert items into the bag without exceeding the capacity $B$ while maximising the total values (i.e., maximising $\sum_{h=1}^i p_h*v_h$ subject to (1) $p_h=0$ or 1, (2) $\sum_{h=1}^i p_h*w_h \leq B$ ).
Problem B: we have the same inputs and constraints as A. The objective function is different which is minimizing $B-\sum_{h=1}^i p_h*v_h$.
Approximation ratio analysis: Suppose $X$ is the value returned by an approximate algorithm for Problem A, $OPT$ is the optimal value. Then for problem A, the ratio is $\alpha \leq X/OPT$. If the algorithm is greedy algorithm, $\alpha$ is $1/2$. On the other hand, for problem B, the ratio is $(B-X)/(B-OPT)$ which can be infinity large when $OPT$ is close to $B$.
So my question is: (1) can we use approximate algorithms in problem A to solve problem B with approximation ratios? (2) Even if we have specialised algorithms for problem B, the denominator $(B-OPT)$ still can be very small. Can we find approximate solutions for problem B?
The answer to Question (1) is no.  The answer to Question (2) is yes.  Here are the details.
I'll work with the following equivalent problem formulations.  For the input, we are given $n$ pairs of values $(v_1, w_1), (v_2, w_2), \ldots, (v_n, w_n)$ in $\mathbb R^2_+$.
Problem A. Find $\max\big\{ \sum_{i\not\in S} v_i : S\subseteq [n],\, \sum_{i\not\in S} w_i \le \sum_{i=1}^n v_i\big\}$.
Problem B. Find $\min\big\{ \sum_{i\in S} v_i : S\subseteq [n],\, \sum_{i\in S} w_i \ge \sum_{i=1}^n w_i-v_i\big\}$.
(By calculation, these problems are equivalent to those in the post. Note that the first is a special case of the standard KNAPSACK problem.  As discussed further in the proof of Theorem 2 below, the second is a special case of a sort of inverse of KNAPSACK.)
Theorem 1. The answer to Question 1 is no.  Specifically, for any $\epsilon&gt;0$, there is a polynomial-time $(1+\epsilon)$-approximation algorithm for Problem A that has infinite approximation ratio for Problem B.
Theorem 2. The answer to Question 2 is yes.  Specifically, there is  polynomial-time $2$-approximation algorithm for Problem B.
Proof of Theorem 1.  First consider the instance $I=((0,\epsilon), (\epsilon, \epsilon), (1, 1))$.  The optimal solution is $S^*=\{1\}$, giving value $1+\epsilon$ for Problem A and $0$ for Problem B.  The solution $S=\{1,2\}$ gives value $1$ for Problem A and $\epsilon$ for Problem B.  So $S$ is a $(1+\epsilon)$-approximate solution for Problem A, but has ratio $\epsilon/0=\infty$ for Problem B.  Now consider an algorithm that, given this instance $I$, returns $S$, and given any other instance $I'$, returns a $(1+\epsilon)$-approximation solution for that instance $I'$, computed using the standard PTAS for KNAPSACK (thinking of $I'$ as an instance of Problem $A$, which is a special case of KNAPSACK). This is the desired algorithm. $~~~\Box$
Proof sketch for Theorem 2. Remark: The algorithm is similar to a greedy algorithm for Knapsack, and its analysis is similar to the analysis of that algorithm.
We give a 2-approximation algorithm for a slightly more general &quot;inverse knapsack&quot; problem:

Given $(v_1, w_1), \ldots, (v_n, w_n)$ and target $W$, find $\min\big\{\sum_{i\in S} v_i : S\subseteq [n],\, \sum_{i\in S} w_i \ge W\big\}$.

Given input $I=(((v_1, w_1), \ldots, (v_n, w_n)), W)$:

if $W\le 0$: return $\emptyset$

let $h = \arg\min_i \frac{v_i}{\min(W, w_i)}$

let $I'$ be the residual instance obtained from $I$ by deleting $(v_i, w_i)$ and replacing $W$ by $W'=W-w_i$.

recursively compute a solution $S'$ for $I'$

return $\{h\} \cup S'$


By a standard inductive argument, the algorithm returns a valid solution.  To finish we sketch a proof that the solution value is at most twice the optimal.  Consider any execution of the algorithm.  If $W\le 0$ the solution is optimal, so assume $W&gt;0$.
Assume WLOG (by reordering $I$) that the final solution $S$ is $S=[m]=\{1,2,\ldots, m\}$, with each index $i\in S$ being chosen in the $i$th of the $m+1$ calls.  Define instances $I_1$ and $I_2$ as follows.  $I_1$ is obtained from $I$ by replacing $W$ by $W_1=w_1+w_2+\ldots+w_{m-1}$, while $I_2$ is obtained from $I$ by replacing $W$ by $W_2=W-W_1$ and deleting the pairs $(v_1, w_1), \ldots, (v_{m-1}, w_{m-1})$ (this is the instance passed into the final second-to-last recursive call).  Then:

$S_1=[m-1]$ is an optimal solution for $I_1$. (Note that $v_i/w_i \le v_j / w_j$ for all $i\in [m-1]$ and $j\not\in[m-1]$, and $w_1+w_2+\ldots+w_{m-1}=W_1$.  Using this, we can show by a standard greedy perturbation argument that $S_1$ is an optimal solution for the fractional relaxation of the instance $I_1$, where a fractional amount $x_i\in[0,1]$ of each item $i$ can be chosen.  So $S_1$ is also optimal for $I_1$.)

$S_2=\{m\}$ is an optimal solution for $I_2$. (This follows by a similar argument, along with the observation that replacing each $w_i$ in $I_2$ by $w'_i=\min(w_i, W)$ doesn't change the optimal value.)

The optimal value for $I_1$ is at most the optimal value for $I$. (This follows from the definition of $I_1$, as any solution for $I$ gives a solution for $I_1$.)

The optimal value for $I_2$ is at most the optimal value for $I$. (Consider the instance $I''$ obtained from $I$ by replacing each $v_i$ with $i\in[m-1]$ by $v'_i=0$.  Clearly the optimal value for $I''$ is a lower bound on the optimal value for $I$.  There is an optimal solution for $I''$ that includes all the indices in $[m-1]$.  The remaining part of that solution gives a solution for $I_2$ of the same value.)


From the preceding four observations, it follows that the cost of the final solution $S=S_1\cup S_2$ is at most twice the optimal value for $I$.$~~~\Box$