2
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ (1) No, for the reason you point out. (2) It depends on the particular problem. $\endgroup$
    – Neal Young
    May 26 at 13:02
  • $\begingroup$ Another example of this phenomenon is that there are NP-optimization problems whose decision version is NPC which can be approximated within a constant (or even any constant) while others cannot even be approximated within a factor of $n^{1-\epsilon}$ in poly-time (unless P=NP). However such problems are all reducible to each-other in polynomial time with regards to computing the exact optimum. $\endgroup$
    – Tassle
    May 26 at 14:53
  • $\begingroup$ @NealYoung Thanks for reply. I have two follow-up questions. (1) I have given the particular definition of problem B above, can we prove whether problem B can be approximated? Based on the equivalence of problem A and B, problem B should be also weakly NP-hard as problem A. (2)Does the weakly NP-hardness of problem B indicate that problem B must can be approximated or approximated in polynomial time? $\endgroup$ May 27 at 3:49
  • $\begingroup$ @Tassle Please have a look at my questions in the last comment. $\endgroup$ May 27 at 3:50
  • $\begingroup$ @NealYoung The objective $B-\sum_h p_hv_h$ cannot be negative. The second term is at most $B$ due to the constraints that $B=\sum_h v_h$ and $0<v_h\leq w_h$. When the second term is $B$, all items can be chosen into the bag, which is very straightforward and a very trivial case of subset-sum problem. Thus, the value range of optimal solution for problem B is within $[0,B]$. I am wondering whether problem B can be approximated (the usual notion of approximation ratio does apply). $\endgroup$ May 27 at 13:16
2
$\begingroup$

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>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 "inverse knapsack" 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)$:

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

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

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

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

  5. 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>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$

$\endgroup$
1
  • $\begingroup$ FWIW I believe it should be easy to adapt the PTAS for KNAPSACK to obtain a PTAS for the "inverse Knapsack" problem in the proof, and therefore for Problem B. $\endgroup$
    – Neal Young
    May 28 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.