We are given N sets, each of which has a finite number of pairs $(x_i,y_i)$.

$M_1=\{(0,0), (x_{1,1},y_{1,1}), ...\}$


$M_N=\{(0,0), (x_{1,N},y_{1,N}), ...\}$

The problem is to select one and only one item from each set such that

$Min \{\displaystyle\sum_{j=1...N}(x_{i,j})\}$

s.t. $\displaystyle\sum_{j=1..N}(y_{i,j}) > R$

where $R$ is a given constant.

Is there any classic problem similar to this? or what is known about this class of problems?

  • $\begingroup$ It's a generalization of KNAPSACK. $\endgroup$ – Yuval Filmus Mar 4 '16 at 10:03

The problem you have given is similar to KNAPSACK as Yuval Filmus mentioned.

KNAPSACK problem is defined as:

maximize $\sum_{i=1}^n v_i x_i$
subject to $\sum_{i=1}^n w_i x_i \leq W$ and $x_i \in \{0,1\}. $

I assume the pair (0,0) is used so that you may not choose pairs for some of the $M_j$'s. Otherwise (0,0) pair is irrelevant in the problem.

If this is so, then your problem can be easily shown to be NP-complete. We can reduce KNAPSACK to your problem by taking $N=n$ and have each $M_j$ as a copy to the KNAPSACK instance (after negating $v_i$'s and $w_i$'s of course).

If pair (0,0) is not used in a way that I described above, then too you can circumvent the issue by adding $N$ pairs $(x_{N+i,j},y_{N+i,j})$, for $1\leq i \leq N$ in set $M_j$ for $1 \leq j \leq N$, so that each $M_j$ has now additional $N$ pairs (total of $2N+1$). Each $x_{N+i,j} = y_{N+i,j} = 0$ for all $i$'s and $j$'s.

If you say that each pair need to be distinct, then we can take $x_{N+i,j} = y_{N+i,j} = \epsilon_{i}$ to make each pair distinct, where $\epsilon_{i} \ll 1$ is an arbitrarily very small quantity. We also replace $R$ by $R+\Sigma_i \epsilon_i$.

| cite | improve this answer | |
  • $\begingroup$ It is a little bit different from KNAPSACK, as we have to pick one and only one item from each set. Am I right? $\endgroup$ – Farzad Mar 4 '16 at 11:24
  • $\begingroup$ No, this is exactly knapsack. Each set represents an item, which you can either pick or not. These are the two "items" that you select from the set. $\endgroup$ – Yuval Filmus Mar 4 '16 at 12:26

As Shreesh mentioned, you can reduce 0-1 knapsack to this problem in this way: In each set, only keep the (0, 0) pair and the pair with the most y to x ratio. the (0, 0) corresponds to setting $x_i$ in knapsack to be zero. Considering that each $y_i$ corresponds to $ w_i $ in knapsack, and considering each $x_i$ in your problem as $v_i$ in knapsack, by setting $ R $ as $ (\displaystyle\sum_{j=1...N}y_j\ )- W $, you can solve knapsack by solving this problem and giving the opposite answer as the answer to 0-1 knapsack.

| cite | improve this answer | |

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.